Cod sursă (job #420232)

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef pair<short,short> PII;

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

int n;
PII p1[505][505], p2[505][505];
short c[505][505];

bool ok(int x, int y, int t) {
    if (x < 0 || x >= n || y < 0 || y >= n || c[x][y] != t) return false;
    return true;
}

PII Find1(PII x) { return (x == p1[x.fi][x.se] ? x : p1[x.fi][x.se] = Find1(p1[x.fi][x.se])); }
PII Find2(PII x) { return (x == p2[x.fi][x.se] ? x : p2[x.fi][x.se] = Find2(p2[x.fi][x.se])); }
void Union1(PII x, PII y) {
    PII px = Find1(x), py = Find1(y);
    if (px == py) return;
    if (c[x.fi][x.se] == 1) {
        if (px.se <= py.se) {
            p1[py.fi][py.se] = px;
        } else p1[px.fi][px.se] = py;
    } else {
        if (px.fi <= py.fi) {
            p1[py.fi][py.se] = px;
        } else p1[px.fi][px.se] = py;
    }
}
void Union2(PII x, PII y) {
    PII px = Find2(x), py = Find2(y);
    if (px == py) return;
    if (c[x.fi][x.se] == 1) {
        if (px.se >= py.se) {
            p2[py.fi][py.se] = px;
        } else p2[px.fi][px.se] = py;
    } else {
        if (px.fi >= py.fi) {
            p2[py.fi][py.se] = px;
        } else p2[px.fi][px.se] = py;
    }
}

int main() {
    freopen("hex.in","r",stdin);
    freopen("hex.out","w",stdout);

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        p1[i][j] = p2[i][j] = {i,j};
    for (int i = 0; i < n*n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        x--; y--;
        c[x][y] = (i % 2) + 1;
        for (int j = 0; j < 6; j++) {
            if (ok(x+dx[j],y+dy[j],c[x][y])) {
                Union1({x,y},{x+dx[j],y+dy[j]});
                Union2({x,y},{x+dx[j],y+dy[j]});
                //cout << x+dx[j] << ' ' << y+dy[j] << ' ' << c[x+dx[j]][y+dy[j]] << " -> " << Find1({x,y}).fi << ' ' << Find1({x,y}).se << " : ";
            }
        }
        //cout << '\n';

        PII par = Find1({x,y});
        if (c[x][y] == 1) {
            if (par.se == 0) {
                if (Find2(par).se == n-1) {
                    cout << i+1;
                    return 0;
                }
            }
        } else {
            if (par.fi == 0) {
                if (Find2(par).fi == n-1) {
                    cout << i+1;
                    return 0;
                }
            }
        }
    }

}