SRM561 Div1 Medium

550

grundy数を計算する。
木構造にして、赤い点を打った頂点より上を全て削除する。
残った木でも排他的論理和。

const int N = 50 + 5;
bool g[N][N];
bool h[N][N];
int p[N];

const int M = N - 1;

int memo[N];
int grundy(int curr)
{
  int& ret = memo[curr];
  if (ret != -1) return ret;

  set<int> s;
  for (int i = 0; i < N; ++i) {
    if (g[curr][i]) {
      int n = i;
      set<int> vis;
      vis.insert(n);
      while (n != p[n]) vis.insert(n = p[n]);
      int b = 0;
      for (int next = 0; next < N; ++next) {
        if (g[curr][next] && !vis.count(next) && vis.count(p[next])) {
          b ^= grundy(next);
        }
      }
      s.insert(b);
    }
  }

  int res = 0;
  while (s.count(res)) ++res;
  return ret = res;
}

bool contain(int x1, int y1, int r1, int x2, int y2, int r2)
{
  unless (r1 > r2) return false;
  int x = x1 - x2;
  int y = y1 - y2;
  int r = r1 - r2;
  return x * x + y * y < r * r;
}

class CirclesGame {
public:
  string whoCanWin(vector <int> x, vector <int> y, vector <int> r)
  {
    const string A = "Alice";
    const string B = "Bob";

    const int size = x.size();

    fill(&g[0][0], &g[N - 1][N - 1] + 1, false);
    for (int i = 0; i < size; ++i) {
      for (int j = 0; j < size; ++j) {
        if (i != j) g[i][j] = contain(x[i], y[i], r[i], x[j], y[j], r[j]);
      }
    }
    for (int i = 0; i < size; ++i) {
      g[M][i] = true;
    }

    copy(&g[0][0], &g[N - 1][N - 1] + 1, &h[0][0]);
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        for (int k = 0; k < N; ++k) {
          if (h[i][j] && g[i][k] && g[k][j]) h[i][j] = false;
        }
      }
    }

    for (int i = 0; i < size; ++i) {
      g[i][i] = true;
    }

    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        if (h[i][j]) p[j] = i;
      }
    }
    p[M] = M;

    fill(memo, memo + N, -1);
    return grundy(M) ? A : B;
  }