Cod sursă (job #542628)

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

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

int t, x, y, n;
int a[N][N];
int p[2][N * N];
int c[N][N];
int d[2][N * N + 5][3];
bool u;

bool OK(int i, int j)
{
    return (i >= 1 && j >= 1 && i <= n && j <= n);
}
bool v;
int find(int x, bool u)
{
    if (p[u][x] == x)
        return x;
    else
        return (p[u][x] = find(p[u][x], u));
}

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

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            c[i][j] = (i - 1) * n + j;
            p[0][c[i][j]] = p[1][c[i][j]] = c[i][j];
            a[i][j] = 10;
        }

    for (int i = 1; i <= n * n; ++i) {
        cin >> x >> y;
        if (i % 2)
            u = 0;
        else
            u = 1;
        a[x][y] = u;

        int a1 = find(c[x][y], u);
        if (i % 2) {
            if (y == 1)
                d[u][a1][0] = 1;
            if (y == n)
                d[u][a1][1] = 1;
        }
        else {
            if (x == 1)
                d[u][a1][0] = 1;
            if (x == n)
                d[u][a1][1] = 1;
        }
        if (d[u][a1][0] && d[u][a1][1]) {
            cout << i;
            return 0;
        }

        for (int d1 = 0; d1 < 6; ++d1) {
            int i2 = x + dx[d1];
            int j2 = y + dy[d1];
            if (!OK(i2, j2) || a[i2][j2] != u)
                continue;
            int b = find(c[i2][j2], u);
            a1 = find(c[x][y], u);
            if (b != a1) {
                p[u][b] = a1;
                d[u][a1][0] = max(d[u][a1][0], d[u][b][0]);
                d[u][a1][1] = max(d[u][a1][1], d[u][b][1]);
            }
        }
        a1 = find(c[x][y], u);
        if (d[u][a1][0] && d[u][a1][1]) {
            cout << i;
            return 0;
        }
    }

    return 0;
}