Cod sursă (job #816298)

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int MAX_N = 500;
const int dx[] = {-1, 1, 0, 0, -1, 1};
const int dy[] = {0, 0, -1, 1, 1, -1};

// DSU (Disjoint Set Union)
struct DSU {
    vector<int> parent, size;

    DSU(int n) : parent(n), size(n, 1) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }

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

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (size[rootX] < size[rootY]) swap(rootX, rootY);
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

int n;
vector<vector<int>> board;
DSU* dsu;
int left_red, right_red, top_blue, bottom_blue;

// Funcție pentru a calcula indexul unui nod în DSU
inline int get_index(int x, int y) {
    return (x - 1) * n + (y - 1);
}

int main() {
    fin >> n;
    int total_nodes = n * n + 4;  // 4 noduri virtuale
    dsu = new DSU(total_nodes);
    board.assign(n + 1, vector<int>(n + 1, 0));

    left_red = n * n;       // Nod virtual pentru coloana 1 (roșu)
    right_red = n * n + 1;  // Nod virtual pentru coloana N (roșu)
    top_blue = n * n + 2;   // Nod virtual pentru linia 1 (albastru)
    bottom_blue = n * n + 3; // Nod virtual pentru linia N (albastru)

    for (int move = 1; move <= n * n; move++) {
        int x, y;
        fin >> x >> y;

        int player = (move % 2 == 1) ? 1 : -1;  // Roșu (1), Albastru (-1)
        board[x][y] = player;
        int curr_idx = get_index(x, y);

        // Conectăm piesa la vecinii de aceeași culoare
        for (int d = 0; d < 6; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && board[nx][ny] == player) {
                dsu->unite(curr_idx, get_index(nx, ny));
            }
        }

        // Conectăm piesele de marginile virtuale
        if (player == 1) {  // Roșu
            if (y == 1) dsu->unite(curr_idx, left_red);
            if (y == n) dsu->unite(curr_idx, right_red);
            if (dsu->connected(left_red, right_red)) {
                fout << move << '\n';
                return 0;
            }
        } else {
            if (x == 1) dsu->unite(curr_idx, top_blue);
            if (x == n) dsu->unite(curr_idx, bottom_blue);
            if (dsu->connected(top_blue, bottom_blue)) {
                fout << move << '\n';
                return 0;
            }
        }
    }
}