Cod sursă (job #646547)

#include <iostream>
#include <fstream>
#include <cstring>

#define NMAX 500

using namespace std;

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

int sef[NMAX * NMAX];
short rg[NMAX * NMAX];
short minim[NMAX * NMAX];
short maxim[NMAX * NMAX];
char color[NMAX * NMAX];
// 0 - unvisited
// 1 - player 1
// 2 - player 2

int dirl[6] = {-1, -1, 0, 0, 1, 1};
int dirc[6] = {0, 1, -1, 1, -1, 0};

int findSet(int u) {
    if (sef[u] == u) return u;
    int tmp, bigBoss = u;
    while (sef[bigBoss] != bigBoss) bigBoss = sef[bigBoss];
    while (sef[u] != u) {
        tmp = sef[u];
        sef[u] = bigBoss;
        u = tmp;
    }
    return bigBoss;
}

void uniteSets(int u, int w) {
    u = findSet(u), w = findSet(w);
    if (rg[u] < rg[w]) {
        sef[u] = w;
    }

    else if (rg[u] > rg[w]) {
        sef[w] = u;

    }
    else {
        sef[w] = u;
        ++rg[u];
    }

    minim[u] = minim[w] = min(minim[w], minim[u]);
    maxim[u] = maxim[w] = max(maxim[w], maxim[u]);
}

int main()
{
    int n, nSquared, x, y, curr, currNeigh, xNeigh, yNeigh, currBoss;
    bool player = 0;
    fin >> n;
    nSquared = n * n;

    memset(sef, -1, sizeof(sef));

    for (int currMove = 0; currMove < nSquared; ++currMove) {
        fin >> x >> y;
        --x, --y;
        curr = x * n + y;
        sef[curr] = curr;
        minim[curr] = maxim[curr] = (player ? x : y);
        color[curr] = player + 1;
        for (int k = 0; k < 6; ++k) {
            xNeigh = x + dirl[k], yNeigh = y + dirc[k], currNeigh = xNeigh * n + yNeigh;
            if (xNeigh < 0 || xNeigh >= n || yNeigh < 0 || yNeigh >= n || color[curr] != color[currNeigh]) continue;
            uniteSets(curr, currNeigh);
        }
        currBoss = findSet(curr);
        if (minim[currBoss] == 0 && maxim[currBoss] == n - 1) {
            fout << currMove + 1;
            break;
        }
        player = !player;
    }

    fin.close();
    fout.close();
    return 0;
}