Cod sursă (job #542340)

#include <bits/stdc++.h>
using namespace std;
#define INDEX(U, V) ((U) * (N + 1) + (V))

int N, ss;
int a[255025];
int stiva[255025];
char ch[2] = {'A', 'R'};
char tabla[505][505];
char b[4][255025];
int c[6][2] = {{0, -1}, {0, 1}, {1, -1}, {-1, 1}, {1, 0}, {-1, 0}};
int j, u, v;

int castiga(int pos, int r) {
  return (b[pos << 1][r]) && (b[(pos << 1) + 1][r]);
}

void aproape(int u, int v, int r) {
  b[0][r] = (u == 1);
  b[1][r] = (u == N);
  b[2][r] = (v == 1);
  b[3][r] = (v == N);
}

int find(int u) {
  for (; a[u]; u = a[u]) {
    stiva[ss++] = u;
  }
  int root = u;
  while (ss) {
    a[stiva[--ss]] = root;
  }
  return root;
}

void unify(int u, int v) {
  int i;
  if (u != v) {
    a[v] = u;
    for (i = 0; i < 4; i++) {
      b[i][u] = b[i][v] = (b[i][u] | b[i][v]);
    }
  }
}

int main(void) {
  ifstream cin("hex.in");
  ofstream cout("hex.out");

  cin>>N;
  int i = 0, ru = 0, M = N * N;
  while ((i <= M) && (!castiga(i & 1, ru))) {
    cin>>u>>v;
    ru = find(INDEX(u, v));
    aproape(u, v, ru);
    tabla[u][v] = ch[++i & 1];
    for (j = 0; j < 6; j++) {
      int u0 = u + c[j][0];
      int v0 = v + c[j][1];
      if (tabla[u0][v0] == tabla[u][v]) {
        unify(ru, find(INDEX(u0, v0)));
      }
    }
  }
  cout<<i;
  return 0;
}