SHOW:
|
|
- or go back to the newest paste.
| 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; |
| 106 | + | cout << arr[0][0] << " " << arr[0][0] << endl; |
| 107 | } else {
| |
| 108 | cout << ans << endl; | |
| 109 | cout << XY.first << " " << XY.second << endl; | |
| 110 | } | |
| 111 | } |
