Google Code Jam 2019 Round 3: Datacenter Duplex

Code Jam - Google’s Coding Competitions

Adding the edges without making any cycles as many as possible, we finally obtain the answer if the answer exists. We don't have to consider the order of adding edges. It is easy to imagine why this holds by checking some actual cases.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct unionfind {
  vector<int> A;
  int cnt;

  unionfind(int n) : A(n, -1), cnt(n) {}

  int find(int x) {
    if (A[x] < 0) return x;
    return A[x] = find(A[x]);
  }

  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (A[x] > A[y]) swap(x, y);
    A[x] += A[y];
    A[y] = x;
    cnt--;
    return true;
  }

  int size(int x) {
    return -A[find(x)];
  }
};

void solve() {
  int h, w;
  cin >> h >> w;
  vector<string> g(h);
  for (int i = 0; i < h; i++) {
    cin >> g[i];
  }
  auto f = [&](int i, int j) { return i * w + j; };
  unionfind uf(h * w);
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (i + 1 < h && g[i][j] == g[i + 1][j]) uf.unite(f(i, j), f(i + 1, j));
      if (j + 1 < w && g[i][j] == g[i][j + 1]) uf.unite(f(i, j), f(i, j + 1));
    }
  }
  vector<string> ans(h - 1, string(w - 1, '.'));
  for (int i = 0; i < h - 1; i++) {
    for (int j = 0; j < w - 1; j++) {
      if (g[i][j] == g[i + 1][j + 1] && uf.unite(f(i, j), f(i + 1, j + 1))) {
        ans[i][j] = '\\';
      } else if (g[i][j + 1] == g[i + 1][j] && uf.unite(f(i, j + 1), f(i + 1, j)))  {
        ans[i][j] = '/';
      }
    }
  }
  if (uf.cnt != 2) {
    cout << "IMPOSSIBLE\n";
    return;
  }
  cout << "POSSIBLE\n";
  for (int i = 0; i < h - 1; i++) {
    cout << ans[i] << '\n';
  }
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  for (int i = 1; i <= T; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
}