Cod sursă (job #420041)

#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[250005], m, dad[505][505], mx[250005], mn[250005];
int ma[502][502], 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;

    mx[b] = max(mx[a], mx[b]);
    mn[b] = min(mn[a], mn[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;
        }
    }
    
    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 {
                mn[dad[x][y]] = min(mn[dad[x][y]], x);
                mx[dad[x][y]] = max(mx[dad[x][y]], x);
            }

            if (mn[dad[x][y]] == 1 && mx[dad[x][y]] == n)
                return cout << i, 0;
        }
    }

	return 0;
}