Cod sursă (job #770666)

#include <bits/stdc++.h>
 
using namespace std;
 
#define nmax 501
#define nmax2 250001
 
int n;
 
struct {
    bitset<nmax> data[nmax];
} matrix[2];
 
#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 x, int y) {
    return x > 0 && y > 0 && x <= n && y <= n;
}
 
int roots[nmax2];
 
inline int get_root(int x) {
    int r = x;
    while (r != roots[r]) {
        r = roots[r];
    }
 
    int t;
    while (x != r) {
        t = roots[x];
        roots[x] = r;
        x = t;
    }
    return r;
}
 
int blue;
inline void join(int x, int y) {
    int rx = get_root(x);
    int ry = get_root(y);
 
    if (blue) {
        if (rx < ry) {
            roots[ry] = rx;
        } else {
            roots[rx] = ry;
        }
    } else {
        if (rx > ry) {
            roots[ry] = rx;
        } else {
            roots[rx] = ry;
        }
    }
}
 
inline bool check(int x, int y) {
    return get_root(x) == get_root(y);
}
 
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[i] = i;
    }
 
    int cnt = 0;
    for (int i = 0, x, y; i < n2; i++) {
        scanf("%d%d", &y, &x);
 
        cnt++;
        blue = i % 2;
        matrix[blue].data[x][y] = true;
        for (int j = 0; j < maxdir; j++) {
            int new_x = x + x_dir[j];
            int new_y = y + y_dir[j];
 
            if (check_bounds(new_x, new_y)) {
                int idx1 = n * (y - 1) + x;
                int idx2 = n * (new_y - 1) + new_x;
                if (matrix[blue].data[new_x][new_y] && !check(idx1, idx2)) {
                    join(idx1, idx2);
                }
            }
 
            if (blue) {
                for (int k = 1, rk; k <= n; k++) {
                    rk = get_root(n * (n - 1) + k);
                    if (rk >= 1 && rk <= n) {
                        i = n2;
                        j = maxdir;
                        break;
                    }
                }
            } else {
                for (int k = 1, rk; k <= n; k++) {
                    rk = get_root((k - 1) * n + 1);
                    if (rk % n == 0) {
                        i = n2;
                        j = maxdir;
                        break;
                    }
                }
            }
        }
    }
 
    cout << cnt << "\n";
 
    return 0;
}