Cod sursă (job #542609)

#include <bits/stdc++.h>

using namespace std;

ifstream fin("hex.in");
ofstream fout("hex.out");

const int NMAX = 500 * 500;
int dl[6] = { 1, 1, -1, -1, 0, 0 };
int dc[6] = { 0, -1, 1, 0, -1, 1 };

short int f[501][501];
int p[NMAX + 1], Rank[NMAX + 1];
int v[NMAX + 1];
int n, l, c;

int cod(int x, int y)
{
    return (x - 1) * n + y;
}

int find(int x)
{
    if (p[x] != x)
        find(p[x]);
    else
        return x;
}

bitset<501> b[501];

void Union(int x, int y)
{
    int r1 = find(x);
    int r2 = find(y);
    if (r1 != r2) {
        if (Rank[r1] < Rank[r2]) {
            b[r2] |= b[r1];
            Rank[r2] += Rank[r1];
            p[r1] = r2;
        }
        else {
            b[r1] |= b[r2];
            Rank[r1] += Rank[r2];
            p[r2] = r1;
        }
    }
}
int main()
{
    fin >> n;
    for (int i = 1; i <= n * n; i++) {
        p[i] = i;
        Rank[i] = 1;
    }
    for (int i = 1; i <= n * n; i++) {
        fin >> l >> c;
        f[l][c] = (i & 1) + 1;
        int root = find(cod(l, c));
        Rank[cod(l, c)] = 1;
        b[root][l] = true;
        for (int j = 0; j < 6; j++) {
            int l1 = l + dl[j];
            int c1 = c + dc[j];
            if (f[l1][c1] == (i & 1) + 1) {
                Union(cod(l, c), cod(l1, c1));
            }
        }
        if (i % 2 == 1)
            for (int j = n * (n - 1) + 1; j <= n * n; j++) {
                int val = find(j);
                bool ok = true;
                for (int k = 1; k <= n; k++)
                    if (b[val][k] == 0) {
                        ok = false;
                        break;
                    }
                if (ok) {
                    fout << i;
                    return 0;
                }
            }
        else
            for (int j = n; j <= n * n; j += n) {
                int val = find(j);
                bool ok = true;
                for (int k = 1; k <= n; k++)
                    if (b[val][k] == 0) {
                        ok = false;
                        break;
                    }
                if (ok) {
                    fout << i;
                    return 0;
                }
            }
    }
    return 0;
}