Cod sursă (job #354856)

#include <fstream>
#include <vector>

using namespace std;

ifstream cin ("hex.in");
ofstream cout ("hex.out");

vector < int > dir_i = {-1, -1, 0, 1, 1, 0};
vector < int > dir_j = {0, 1, 1, 0, -1, -1};

class D_Set {
public:

  D_Set () {
    
    cin >> n;

    mat.resize (n + 1);
    root.resize (n + 1);
    lvl.resize (n + 1);
    propr.resize (n + 1);

    for (int i = 1; i <= n; ++ i) {
      mat[i].resize (n + 1);
      root[i].resize (n + 1);
      lvl[i].resize (n + 1);
      propr[i].resize (n + 1);
    }

    int ind = 0;
    for (int i = 1; i <= n; ++ i) {
      for (int j = 1; j <= n; ++ j) {
        mat[i][j] = 0;
        root[i][j].i = i;
        root[i][j].j = j;
        lvl[i][j] = 1;
        
        if (i == 1) {
          propr[i][j].hit_top = true;
        }

        if (i == n) {
          propr[i][j].hit_bot = true;
        }
        
        if (j == 1) {
          propr[i][j].hit_left = true;
        }

        if (j == n) {
          propr[i][j].hit_right = true;
        }
      }
    }

    done = false;
  }

  void Solve () {
  
    Poz cur;
    int ans = 0;
    for (int i = 1; i <= n * n; ++ i) {

      cin >> cur.i >> cur.j;
  
      ++ ans;
      if (i % 2 == 1) {
        mat[cur.i][cur.j] = 1;
      }
      else {
        mat[cur.i][cur.j] = 2;
      }
      
      Poz neigh;
      for (int d = 0; d < 6; ++ d) {

        neigh.i = cur.i + dir_i[d];
        neigh.j = cur.j + dir_j[d];

        if (not Is_Good (neigh)) {
          continue;
        }

        if (mat[neigh.i][neigh.j] != mat[cur.i][cur.j]) {
          continue;
        }
  
        Link (cur, neigh);

        if (done) {
          cout << ans << '\n';
          return;
        }
      }
    }
  }

private:
  
  struct Poz {

    short int i, j;
    bool operator == (Poz x) {
      return this -> i == x.i and this -> j == x.j;
    }

    bool operator != (Poz x) {
      return  not (*this == x);
    }

    void operator = (Poz x) {
      this -> i = x.i;
      this -> j = x.j;
    }
  };

  struct Propr {

    Propr () {
      hit_top = false;
      hit_bot = false;
      hit_left = false;
      hit_right = false;
    }

    bool hit_top, hit_bot, hit_left, hit_right;
  };

  int n;
  bool done;
  vector < vector < Poz > > root;
  vector < vector < Propr > > propr;
  vector < vector < short int > > mat, lvl;
 
  Poz Get_Root (Poz x) {

    Poz r = x;
    while (r != root[r.i][r.j]) {
      r = root[r.i][r.j];
    }

    while (x != root[x.i][x.j]) {
      Poz aux = root[x.i][x.j];
      root[x.i][x.j] = r;
      x = aux;
    }

    return r;
  }

  void Link (Poz x, Poz y) {

    x = Get_Root (x);
    y = Get_Root (y);

    if (x == y) {
      return;
    }
  
    if (lvl[x.i][x.j] == lvl[y.i][y.j]) {
      ++ lvl[x.i][x.j];
    }
    else if (lvl[x.i][x.j] < lvl[y.i][y.j]) {
      swap (x, y);
    }

    root[y.i][y.j] = x;

    if (mat[x.i][x.j] == 1) {
      propr[x.i][x.j].hit_left |= propr[y.i][y.j].hit_left;
      propr[x.i][x.j].hit_right |= propr[y.i][y.j].hit_right;
      if (propr[x.i][x.j].hit_left and propr[x.i][x.j].hit_right) {
        done = true;
      }
    }
    else {
      propr[x.i][x.j].hit_top |= propr[y.i][y.j].hit_top;
      propr[x.i][x.j].hit_bot |= propr[y.i][y.j].hit_bot;
      if (propr[x.i][x.j].hit_top and propr[x.i][x.j].hit_bot) {
        done = true;
      }
    }
  }

  bool Is_Good (Poz k) {
    return k.i >= 1 and k.i <= n and k.j >= 1 and k.j <= n;
  }
};

int main () {
  
  D_Set D;
  D.Solve (); 
}