Cod sursă (job #646546)

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

#define NMAX 500

using namespace std;

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

int sef[2][NMAX * NMAX];
short rg[2][NMAX * NMAX];
short minim[2][NMAX * NMAX];
short maxim[2][NMAX * NMAX];

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

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

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

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

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

    minim[player][u] = minim[player][w] = min(minim[player][w], minim[player][u]);
    maxim[player][u] = maxim[player][w] = max(maxim[player][w], maxim[player][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[player][curr] = curr;
        minim[player][curr] = maxim[player][curr] = (player ? x : y);
        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 || sef[player][currNeigh] == -1) continue;
            uniteSets(player, curr, currNeigh);
        }
        currBoss = findSet(player, curr);
        if (minim[player][currBoss] == 0 && maxim[player][currBoss] == n - 1) {
            fout << currMove + 1;
            break;
        }
        player = !player;
    }

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