Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(x) (x).begin(),(x).end()
- using namespace std;
- const int MSIZE = 1000001;
- struct DSU {
- vector<int> p, d;
- DSU(int n) {
- p.assign(n, 0);
- d.assign(n, 1);
- iota(all(p), 0);
- }
- int get(int v) {
- if (p[v] == v) return v;
- return p[v] = get(p[v]);
- }
- void uni(int a, int b) {
- a = get(a);
- b = get(b);
- if (a == b) return;
- if (d[a] < d[b]) swap(a, b);
- d[a] += d[b];
- p[b] = a;
- }
- };
- int arr[1000][1000];
- __inline__ int get(int x, int y) {
- return x * 1000 + y;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int n, m;
- cin >> n >> m;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- cin >> arr[i][j];
- }
- }
- DSU dsu(MSIZE);
- map<pair<int,int>, vector<pair<int,int> > > mp; // X -> Y {(indXi, indYi)}
- bool allEqual = true;
- // compress
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- allEqual &= arr[i][j] == arr[0][0];
- if (i && arr[i - 1][j] == arr[i][j]) {
- dsu.uni(get(i - 1, j), get(i, j));
- }
- if (j && arr[i][j - 1] == arr[i][j]) {
- dsu.uni(get(i, j - 1), get(i, j));
- }
- }
- }
- // build graph
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- if (i && arr[i - 1][j] != arr[i][j]) {
- int x = arr[i - 1][j];
- int y = arr[i][j];
- if (x > y) swap(x, y);
- mp[{x, y}].push_back({dsu.get(get(i - 1, j)), dsu.get(get(i, j))});
- }
- if (j && arr[i][j - 1] != arr[i][j]) {
- int x = arr[i][j - 1];
- int y = arr[i][j];
- if (x > y) swap(x, y);
- mp[{x, y}].push_back({dsu.get(get(i, j - 1)), dsu.get(get(i, j))});
- }
- }
- }
- for (auto& [key, v] : mp) {
- sort(all(v));
- v.erase(unique(all(v)), v.end());
- v.shrink_to_fit();
- }
- int ans = 0;
- pair<int,int> XY;
- DSU dsu2(MSIZE);
- for (int i = 0; i < MSIZE; i++) {
- dsu2.d[i] = dsu.d[i];
- }
- for (auto& [xy, st] : mp) {
- int curAns = 0;
- for (auto& [i, j] : st) {
- dsu2.uni(i, j);
- curAns = max(curAns, dsu2.d[dsu2.get(i)]);
- }
- if (ans < curAns) {
- ans = curAns;
- XY = xy;
- }
- for (auto& [i, j] : st) {
- dsu2.p[i] = i;
- dsu2.d[i] = dsu.d[i];
- dsu2.p[j] = j;
- dsu2.d[j] = dsu.d[j];
- }
- }
- if (allEqual) {
- cout << n * m << endl;
- cout << arr[0][0] << " " << arr[0][0] << endl;
- } else {
- cout << ans << endl;
- cout << XY.first << " " << XY.second << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement