fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<int, int>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 1e3;
  12. const int base = maxn + 1;
  13. const int dx[] = {-1, 0, 1, 0};
  14. const int dy[] = {0, 1, 0, -1};
  15.  
  16. int n, leader[base *base + 10], sz[base * base + 10], ans = 0;
  17. ll a[maxn + 10][maxn + 10];
  18. vector<ll> v;
  19. map<int, vector<ii>> mp;
  20. vector<ii> edge[base * base + 10];
  21.  
  22. bool in_matrix(int x, int y)
  23. {
  24.     return x >= 1 && x <= n && y >= 1 && y <= n;
  25. }
  26. int get_node_id(int x, int y)
  27. {
  28.     return (x - 1) * n + y;
  29. }
  30. int get_id(int x)
  31. {
  32.     return lower_bound(v.begin(), v.end(), x) - v.begin();
  33. }
  34. int find_leader(int x)
  35. {
  36.     if (x == leader[x]) return x;
  37.     return leader[x] = find_leader(leader[x]);
  38. }
  39. void connect(int x, int y)
  40. {
  41.     x = find_leader(x);
  42.     y = find_leader(y);
  43.     if (x == y) return ;
  44.     if (sz[x] < sz[y]) swap(x, y);
  45.     sz[x] += sz[y];
  46.     leader[y] = x;
  47.     ans = max(ans, sz[x]);
  48. }
  49.  
  50. int main()
  51. {
  52.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  53.     if (fopen("ROBOT.INP", "r"))
  54.     {
  55.         freopen("ROBOT.INP", "r", stdin);
  56.         freopen("ROBOT.OUT", "w", stdout);
  57.     }
  58.  
  59.     cin >> n;
  60.     for (int i = 1; i <= n; i++)
  61.         for (int j = 1; j <= n; j++)
  62.             cin >> a[i][j];
  63.     for (int i = 1; i <= get_node_id(n, n); i++)
  64.     {
  65.         leader[i] = i;
  66.         sz[i] = 1;
  67.     }
  68.     for (int i = 1; i <= n; i++)
  69.     {
  70.         for (int j = 1; j <= n; j++)
  71.         {
  72.             for (int k = 0; k < 4; k++)
  73.             {
  74.                 int ni = i + dx[k];
  75.                 int nj = j + dy[k];
  76.                 if (!in_matrix(ni, nj)) continue;
  77.                 v.push_back(abs(a[i][j] - a[ni][nj]));
  78.             }
  79.         }
  80.     }
  81.     sort(v.begin(), v.end());
  82.     v.resize(unique(v.begin(), v.end()) - v.begin());
  83.     for (int i = 1; i <= n; i++)
  84.     {
  85.         for (int j = 1; j <= n; j++)
  86.         {
  87.             for (int k = 0; k < 4; k++)
  88.             {
  89.                 int ni = i + dx[k];
  90.                 int nj = j + dy[k];
  91.                 if (!in_matrix(ni, nj)) continue;
  92.                 edge[get_id(abs(a[i][j] - a[ni][nj]))].push_back({get_node_id(i, j), get_node_id(ni, nj)});
  93.             }
  94.         }
  95.     }
  96.     for (int i = 0; i < v.size(); i++)
  97.     {
  98.         for (ii p : edge[i])
  99.         {
  100.             int a = p.fi;
  101.             int b = p.se;
  102.             connect(a, b);
  103.         }
  104.         for (ii p : edge[i])
  105.         {
  106.             int a = p.fi;
  107.             int b = p.se;
  108.             leader[a] = a;
  109.             leader[b] = b;
  110.             sz[a] = sz[b] = 1;
  111.         }
  112.     }
  113.     cout << ans;
  114. }
Success #stdin #stdout 0.01s 27784KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/J7ND7r
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!