Advertisement
999ms

task G Death

Sep 22nd, 2019
185
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(),(x).end()
  3.  
  4. using namespace std;
  5.  
  6. const int MSIZE = 1000001;
  7. struct DSU {
  8.     vector<int> p, d;
  9.     DSU(int n) {
  10.         p.assign(n, 0);
  11.         d.assign(n, 1);
  12.         iota(all(p), 0);
  13.     }
  14.     int get(int v) {
  15.         if (p[v] == v) return v;
  16.         return p[v] = get(p[v]);
  17.     }
  18.     void uni(int a, int b) {
  19.         a = get(a);
  20.         b = get(b);
  21.         if (a == b) return;
  22.         if (d[a] < d[b]) swap(a, b);
  23.         d[a] += d[b];
  24.         p[b] = a;
  25.     }
  26. };
  27.  
  28. int arr[1000][1000];
  29.  
  30. __inline__ int get(int x, int y) {
  31.     return x * 1000 + y;
  32. }
  33.  
  34. int main() {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(nullptr);
  37.     int n, m;
  38.     cin >> n >> m;
  39.     for (int i = 0; i < n; i++) {
  40.         for (int j = 0; j < m; j++) {
  41.             cin >> arr[i][j];
  42.         }
  43.     }
  44.     DSU dsu(MSIZE);
  45.     map<pair<int,int>, vector<pair<int,int> > > mp; // X -> Y {(indXi, indYi)}
  46.     bool allEqual = true;
  47.     // compress
  48.     for (int i = 0; i < n; i++) {
  49.         for (int j = 0; j < m; j++) {
  50.             allEqual &= arr[i][j] == arr[0][0];
  51.             if (i && arr[i - 1][j] == arr[i][j]) {
  52.                 dsu.uni(get(i - 1, j), get(i, j));
  53.             }
  54.             if (j && arr[i][j - 1] == arr[i][j]) {
  55.                 dsu.uni(get(i, j - 1), get(i, j));
  56.             }
  57.         }
  58.     }
  59.     // build graph
  60.     for (int i = 0; i < n; i++) {
  61.         for (int j = 0; j < m; j++) {
  62.             if (i && arr[i - 1][j] != arr[i][j]) {
  63.                 int x = arr[i -  1][j];
  64.                 int y = arr[i][j];
  65.                 if (x > y) swap(x, y);
  66.                 mp[{x, y}].push_back({dsu.get(get(i - 1, j)), dsu.get(get(i, j))});
  67.             }
  68.             if (j && arr[i][j - 1] != arr[i][j]) {
  69.                 int x = arr[i][j - 1];
  70.                 int y = arr[i][j];
  71.                 if (x > y) swap(x, y);
  72.                 mp[{x, y}].push_back({dsu.get(get(i, j - 1)), dsu.get(get(i, j))});
  73.             }
  74.         }
  75.     }
  76.     for (auto& [key, v] : mp) {
  77.         sort(all(v));
  78.         v.erase(unique(all(v)), v.end());
  79.         v.shrink_to_fit();
  80.     }
  81.     int ans = 0;
  82.     pair<int,int> XY;
  83.     DSU dsu2(MSIZE);
  84.     for (int i = 0; i < MSIZE; i++) {
  85.         dsu2.d[i] = dsu.d[i];
  86.     }
  87.     for (auto& [xy, st] : mp) {
  88.         int curAns = 0;
  89.         for (auto& [i, j] : st) {
  90.             dsu2.uni(i, j);
  91.             curAns = max(curAns, dsu2.d[dsu2.get(i)]);
  92.         }
  93.         if (ans < curAns) {
  94.             ans = curAns;
  95.             XY = xy;
  96.         }
  97.         for (auto& [i, j] : st) {
  98.             dsu2.p[i] = i;
  99.             dsu2.d[i] = dsu.d[i];
  100.             dsu2.p[j] = j;
  101.             dsu2.d[j] = dsu.d[j];
  102.         }
  103.     }
  104.     if (allEqual) {
  105.         cout << n * m << endl;
  106.         cout << arr[0][0] << " " << arr[0][0] << endl;
  107.     } else {
  108.         cout << ans << endl;
  109.         cout << XY.first << " " << XY.second << endl;
  110.     }
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement