Cod sursă (job #420652)

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

int n, i, j, x, y, cn, reln;
int parent[260000], f[510][510], m[2][6] = {{0, 1, 0, - 1, 1, - 1},{1, 0, - 1, 0, - 1, 1}};
bool c[4][260000];

int relate(int x)
{
    if (parent[x] != 0) 
		return parent[x] = relate(parent[x]);
	return x;
}

int main()
{
    ifstream cin("hex.in");
    ofstream cout("hex.out");
    cin >> n;
    for (i = 1; i <= n * n; ++i)
    {
        cin >> x >> y;
        cn = relate(x * (n + 1) + y);
        if (x == 1)
            c[0][cn] = 1;
        if (x == n)
            c[1][cn] = 1;
        if (y == 1)
            c[2][cn] = 1;
        if (y == n)
            c[3][cn] = 1;
        f[x][y] = (i % 2) + 1;
        for (j = 0; j < 6; ++j)
            if (f[x + m[0][j]][y + m[1][j]] == f[x][y])
            {
                reln = relate((x + m[0][j]) * (n + 1) + y + m[1][j]);
                if (cn != reln)
                {
                    parent[reln] = cn;
                    for (int l = 0; l < 4; ++ l)
                        if (c[l][reln])
                            c[l][cn] = 1;
                        else if (c[l][cn])
                            c[l][reln] = 1;
                }
            }
        if ((!(i % 2) && c[0][cn] && c[1][cn]) || (i % 2 && c[2][cn] && c[3][cn]))
        {
        	cout << i;
			return 0;
		}
    }
}