Cod sursă (job #353940)

#include <fstream>
#include <vector>

using namespace std;

class DSet
{
public:
  DSet(int size)
    : fathers_(vector<int>(size, -1)) {}

  void Unite(int a, int b);

  bool SameGroup(int a, int b);

private:
  int Root(int node);

  vector<int> fathers_;
};

void DSet::Unite(int a, int b)
{
  auto ra = Root(a);
  auto rb = Root(b);

  if (ra != rb) {
    fathers_[rb] = ra;
  }
}

bool DSet::SameGroup(int a, int b)
{
  return Root(a) == Root(b);
}

int DSet::Root(int node)
{
  if (fathers_[node] == -1) {
    return node;
  }
  return fathers_[node] = Root(fathers_[node]);
}

typedef pair<int, int> Position;

class MatrixDSet : public DSet
{
public:
  MatrixDSet(int rows, int cols)
    : DSet(rows * cols),
      rows_(rows), cols_(cols) {}

  void Unite(const Position &a, const Position &b);

  bool SameGroup(const Position &a, const Position &b);

private:
  int Index(const Position &pos) const;

  int rows_;
  int cols_;
};

void MatrixDSet::Unite(const Position &a, const Position &b)
{
  auto ia = Index(a);
  auto ib = Index(b);
  DSet::Unite(ia, ib);
}

bool MatrixDSet::SameGroup(const Position &a, const Position &b)
{
  auto ia = Index(a);
  auto ib = Index(b);
  return DSet::SameGroup(ia, ib);
}

int MatrixDSet::Index(const Position &pos) const
{
  return pos.first * cols_ + pos.second;
}

typedef vector<vector<int>> Matrix;

inline bool InBounds(const Matrix &mat, int x, int y)
{
  return x >= 0 && x < (int)mat.size() &&
         y >= 0 && y < (int)mat[0].size();
}

void PlaceToken(Matrix &mat, MatrixDSet &dset, int x, int y, int col)
{
  static const vector<Position> kMods = {
    {-1, 0}, {-1, 1}, {0, 1}, {1, 0}, {1, -1}, {0, -1}
  };

  mat[x][y] = col;

  for (const auto &mod : kMods) {
    auto cx = x + mod.first;
    auto cy = y + mod.second;

    if (InBounds(mat, cx, cy) && mat[cx][cy] == col) {
      dset.Unite({x, y}, {cx, cy});
    }
  }
}

bool CheckWinCol(const Matrix &mat, MatrixDSet &dset, int x, int y, int column)
{
  for (size_t i = 0; i < mat.size(); ++i) {
    if (mat[i][column] != mat[x][y]) {
      continue;
    }
    if (dset.SameGroup({i, column}, {x, y})) {
      return true;
    }
  }
  return false;
}

bool CheckWinRow(const Matrix &mat, MatrixDSet &dset, int x, int y, int row)
{
  for (size_t i = 0; i < mat[0].size(); ++i) {
    if (mat[row][i] != mat[x][y]) {
      continue;
    }
    if (dset.SameGroup({row, i}, {x, y})) {
      return true;
    }
  }
  return false;
}

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

  int n;
  fin >> n;

  Matrix mat(n, vector<int>(n, -1));
  MatrixDSet dset(n, n);

  for (int i = 0; i < n * n; ++i) {
    int col = i % 2;
    int x, y;

    fin >> x >> y;
    x -= 1;
    y -= 1;

    PlaceToken(mat, dset, x, y, col);

    if (i + 1 < 2 * n) {
      continue;
    }

    bool win = false;
    if (col == 0 && (y == 0 || y == n - 1)) {
      win = CheckWinCol(mat, dset, x, y, n - 1 - y);
    } else if (col == 1 && (x == 0 || x == n - 1)) {
      win = CheckWinRow(mat, dset, x, y, n - 1 - x);
    }

    if (win) {
      fout << i + 1 << "\n";
      break;
    }
  }
  return 0;
}