代码

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
using namespace std;
 
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;

template <typename _T>
inline void read(_T &f) {
    f = 0; _T fu = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }
    while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
    f *= fu;
}

template <typename T>
void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x < 10) putchar(x + 48);
    else print(x / 10), putchar(x % 10 + 48);
}

template <typename T>
void print(T x, char t) {
    print(x); putchar(t);
}

const int N = 2005;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

struct ele {
	int ca, cb, u, v;
	ele (int a = 0, int b = 0, int c = 0, int d = 0) : ca(a), cb(b), u(c), v(d) {}
	bool operator < (const ele A) const {
		if (ca != A.ca) return ca < A.ca;
		return cb < A.cb;
	}
} edg[N * N * 2], tmp[N * N * 2];

struct edge_t { int v, next; } G[N * N * 4];

pii q[N * N]; int qq[N * N];
int a[N][N], id[N][N], ti[N * N], big[N * N], head[N * N], tax[N * N];
int n, m, tot, dfn, cnt, ans, edgtot, hd, tl;

inline void addedge(int u, int v) {
	G[++edgtot] = (edge_t) {v, head[u]}, head[u] = edgtot;
	G[++edgtot] = (edge_t) {u, head[v]}, head[v] = edgtot;
}

void bfs(int s) {
	if (ti[s] == dfn) return;
	ti[s] = dfn;
	int sum = big[s];
	hd = 1; tl = 0;
	qq[++tl] = s;
	while (hd <= tl) {
		int u = qq[hd]; ++hd;
		for (int i = head[u]; i; i = G[i].next) {
			int v = G[i].v;
			if (ti[v] == dfn) continue;
			ti[v] = dfn;
			sum += big[v];
			qq[++tl] = v;
		}
	}
	ans = max(ans, sum);
}

int main() {
n=m=2000;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) a[i][j]=rand()%(100)+1;
	}
	hd = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!id[i][j]) {
				++tot;
				q[++tl] = make_pair(i, j);
				id[i][j] = tot; big[tot] = 1;
				while (hd <= tl) {
					pii u = q[hd]; ++hd;
					for (int k = 0; k < 4; k++) {
						int x = u.first + dx[k], y = u.second + dy[k];
						if (x <= 0 || y <= 0 || x > n || y > m) continue;
						if (a[x][y] != a[i][j] || id[x][y]) continue;
						id[x][y] = tot; q[++tl] = make_pair(x, y); ++big[tot];
					}
				}
				ans = max(ans, big[tot]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int k = 0; k < 4; k += 2) {
				int x = i + dx[k], y = j + dy[k];
				if (x <= 0 || y <= 0 || x > n || y > m) continue;
				if (id[i][j] != id[x][y]) {
					int ca = a[i][j], cb = a[x][y];
					if (ca > cb) swap(ca, cb);
					edg[++cnt] = ele(ca, cb, id[i][j], id[x][y]);
				}
			}
		}
	}
	// sort(edg + 1, edg + cnt + 1);
	for (int i = 1; i <= cnt; i++) ++tax[edg[i].cb];
	for (int i = 1; i <= tot; i++) tax[i] += tax[i - 1];
	for (int i = 1; i <= cnt; i++) tmp[tax[edg[i].cb]--] = edg[i];
	memset(tax, 0, sizeof(tax));
	for (int i = 1; i <= cnt; i++) ++tax[tmp[i].ca];
	for (int i = 1; i <= tot; i++) tax[i] += tax[i - 1];
	for (int i = cnt; i >= 1; i--) edg[tax[tmp[i].ca]--] = tmp[i];
	for (int l = 1, r; l <= cnt; l = r + 1) {
		// cerr << l << endl;
		r = l;
		while (r < cnt && edg[r + 1].ca == edg[l].ca && edg[r + 1].cb == edg[l].cb) ++r;
		for (int i = l; i <= r; i++) head[edg[i].u] = head[edg[i].v] = 0;
		edgtot = 0;
		for (int i = l; i <= r; i++) addedge(edg[i].u, edg[i].v);
		++dfn;
		for (int i = l; i <= r; i++) bfs(edg[i].u), bfs(edg[i].v);
		// fprintf(stderr, "ca = %d, cb = %d, ans = %d\n", edg[l].ca, edg[l].cb, ans);
	}
	print(ans, '\n');
	return 0;
}

评测结果