Cod sursă (job #420033)

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair< int , int > PII;

int n, pr[100100], m, dad[505][505], mx[505 * 505], mn[505 * 505], mx1[505 * 505], mn1[505 * 505];
int ma[505][505];
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)
{
	a = find(a);
	b = find(b);
	pr[a] = 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 * n || ny < 1 || ny > n * n || ma[nx][ny] != u) continue;
            unite(dad[x][y], dad[nx][ny]);
            dad[x][y] = find(dad[x][y]);
            dad[nx][ny] = dad[x][y];

            //cout << x << " " << y << " " << nx << " " << ny << " " << dad[x][y] << "\n";

            if (u == 0) {
                mn[dad[x][y]] = min(mn[dad[x][y]], y);
                mx[dad[x][y]] = max(mx[dad[x][y]], y);

                // cout << mn[dad[x][y]] << " " << mx[dad[x][y]] << "\n";
            } else {
                mn1[dad[x][y]] = min(mn1[dad[x][y]], x);
                mx1[dad[x][y]] = max(mx1[dad[x][y]], x);
                // cout << mn1[dad[x][y]] << " " << mx1[dad[x][y]] << "!\n";
            }

            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;
}