Cod sursă (job #542603)

#include <bits/stdc++.h>

using namespace std;

int n, pr[250005], m, dad[505][505], mx[250005], mn[250005], mx1[250005], mn1[250005];
int ma[502][502];
int x, a, b;

const int dirx[] = {0, 1, 0, -1, 1, -1};
const int diry[] = {1, 0, -1, 0, -1, 1};
 
int find(int nod)
{
	if (pr[nod] == nod) return nod;
	int p = find(pr[nod]);
	pr[nod] = p;
	return p;
}
 
void unite(int a, int b, bool u)
{
	a = find(a);
	b = find(b);
	pr[a] = b;

	if (u == 0) {
		mx[b] = max(mx[a], mx[b]);
		mn[b] = min(mn[a], mn[b]);
	} else {
		mx1[b] = max(mx1[a], mx1[b]);
		mn1[b] = min(mn1[a], mn1[b]);
	}
}

int main(){
	ifstream cin("hex.in");
	ofstream cout("hex.out");

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int cnt = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dad[i][j] = ++cnt;
			ma[i][j] = -1;
			pr[cnt] = cnt;
			mn[cnt] = 1000000000;
			mn1[cnt] = 1000000000;
		}
	}
	
	bool u = 0; // 0 - red, 1 - blue
	for (int i = 1, x, y; i <= n * n; i++, u = !u) {
		cin >> x >> y;
		ma[x][y] = u;
		for (int k = 0; k < 6; k++) {
			int nx = x + dirx[k];
			int ny = y + diry[k];
			if (nx < 1 || nx > n || ny < 1 || ny > n || ma[nx][ny] != u) continue;
			if (find(dad[x][y]) != find(dad[nx][ny])) {
				unite(dad[x][y], dad[nx][ny], u);
				dad[x][y] = find(dad[x][y]);
				dad[nx][ny] = find(dad[nx][ny]);
			}
			if (u == 0) {
				mn[dad[x][y]] = min(mn[dad[x][y]], y);
				mx[dad[x][y]] = max(mx[dad[x][y]], y);
			} else {
				mn1[dad[x][y]] = min(mn1[dad[x][y]], x);
				mx1[dad[x][y]] = max(mx1[dad[x][y]], x);
			}
			if (mn[dad[x][y]] == 1 && mx[dad[x][y]] == n) return cout << i, 0;
			if (mn1[dad[x][y]] == 1 && mx1[dad[x][y]] == n) return cout << i, 0;
		}
	}

	return 0;
}