Cod sursă (job #357328)

#include <bits/stdc++.h>

using namespace std;

#define nmax 501
#define nmax2 250001
#define pos(x, y) (n * (y - 1) + x)

int n;

char matrix[nmax][nmax];
char type[2][nmax2];

#define maxdir 6
int x_dir[] = {0, 1, 1, 0, -1, -1};
int y_dir[] = {-1, -1, 0, 1, 1, 0};

inline bool check_bounds(int color, int x, int y) {
    return x > 0 && y > 0 && x <= n && y <= n && matrix[x][y] == color;
}

int roots[2][nmax2];

inline int get_root(int color, int x) {
    int r = x;
    while (r != roots[color][r]) {
        r = roots[color][r];
    }

    int t;
    while (x != r) {
        t = roots[color][x];
        roots[color][x] = r;
        x = t;
    }
    return r;
}

inline int join(int color, int x, int y) {
    int rx = get_root(color, x);
    int ry = get_root(color, y);

    roots[color][rx] = ry;

    type[color][rx] |= type[color][ry];
    type[color][ry] |= type[color][rx];

    return type[color][rx] == 3;
}

int main() {
    freopen("carici.in", "r", stdin);

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

    scanf("%d", &n);
    int n2 = n * n;

    for (int i = 1; i <= n2; i++) {
        roots[0][i] = i;
        roots[1][i] = i;
    }

    for ( int i = 1; i <= n; ++i )
    {
        type[1][ ( i - 1 ) * n + 1 ] = 1;
        type[1][ ( i - 1 ) * n + n ] = 2;
    }

    for ( int i = 1; i <= n; ++i )
    {
        type[0][i] = 1;
        type[0][ ( n - 1 ) * n + i ] = 2;
    }

    int cnt = 0;
    for (int i = 1, x, y; i <= n2; i++) {
        scanf("%d%d", &y, &x);

        cnt++;
        int stop = 0;
        matrix[x][y] = (i & 1) + 1;
        for (int j = 0; j < maxdir; j++) {
            int new_x = x + x_dir[j];
            int new_y = y + y_dir[j];

            if (check_bounds((i & 1) + 1, new_x, new_y)) {
                int ridx1 = get_root(i & 1, pos(x, y));
                int ridx2 = get_root(i & 1, pos(new_x, new_y));

                if (ridx1 != ridx2) {
                    stop |= join(i & 1, ridx1, ridx2);
                }
            }
        }

        if (stop) {
            break;
        }
    }

    cout << cnt << "\n";

    return 0;
}