Cod sursă (job #420595)

#include <bits/stdc++.h>
using namespace std;
ifstream si ("hex.in");
ofstream so ("hex.out");
short t[505][505];
short tata[505][505][2];
short minn[505][505];
short maxx[505][505];
int d[][2] = { {0, 1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1} };

int n;
pair < int, int >
gtata (int x, int y)
{
  int tx = x, ty = y;
  int a, b;
  while (tata[tx][ty][0] != tx || tata[tx][ty][1] != ty)
    {
      a = tx;
      b = ty;
      tx = tata[a][b][0];
      ty = tata[a][b][1];
    }
  while (x != tx || y != ty)
    {
      a = tata[x][y][0];
      b = tata[x][y][1];
      tata[x][y][0] = tx;
      tata[x][y][1] = ty;
      x = a;
      y = b;
    }
  return make_pair (tx, ty);
}

void
unit (int x1, int y1, int x2, int y2)
{
  pair < int, int >t1 = gtata (x1, y1);
  pair < int, int >t2 = gtata (x2, y2);

  if (t1.first != t2.first || t1.second != t2.second)
    {
      tata[t1.first][t1.second][0] = t2.first;
      tata[t1.first][t1.second][1] = t2.second;
      minn[t2.first][t2.second] =
	min (minn[t2.first][t2.second], minn[t1.first][t1.second]);
      maxx[t2.first][t2.second] =
	max (maxx[t2.first][t2.second], maxx[t1.first][t1.second]);
    }
}

bool
comp (int x, int y)
{
  int mn = minn[x][y], mx = maxx[x][y];
  int tx = x, ty = y;
  int a, b;
  while (tata[tx][ty][0] != tx || tata[tx][ty][1] != ty)
    {
      a = tx;
      b = ty;
      tx = tata[a][b][0];
      ty = tata[a][b][1];
      mn = min (mn, (int) minn[tx][ty]);
      mx = max (mx, (int) maxx[tx][ty]);
    }
  minn[tx][ty] = mn;
  maxx[tx][ty] = mx;

  if (mn == 1 && mx == n)
    return true;
  else
    return false;
}

int
main ()
{
  si >> n;
  int x, y, p = 1;
  int q = n * n;
  bool gata = false;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      {
	minn[i][j] = n + 1;
	maxx[i][j] = 0;
      }
  for (int i = 1; !gata && i <= q; ++i)
    {
      si >> x >> y;
      t[x][y] = p;
      tata[x][y][0] = x;
      tata[x][y][1] = y;
      if (p == 1)
	minn[x][y] = maxx[x][y] = y;
      else
	minn[x][y] = maxx[x][y] = x;
      for (int j = 0; j < 6; ++j)
	{
	  if (t[x + d[j][0]][y + d[j][1]] == p)
	    {
	      unit (x, y, x + d[j][0], y + d[j][1]);
	    }
	}
      pair < int, int >tat;
      tat = gtata (x, y);
      p = 3 - p;
      if (comp (x, y))
	{
	  so << i;
	  gata = true;
	}
    }
  return 0;
}