Submission #1307560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307560		lucaskojima	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	343 ms	11616 KiB

coprobber

#include "coprobber.h"
#include "bits/stdc++.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int deg[MAX_N][MAX_N][2];
int win[MAX_N][MAX_N][2];
int los[MAX_N][MAX_N][2];
int nxt[MAX_N][MAX_N];
int P;

int start(int N, bool A[MAX_N][MAX_N]) {
  for (int i = 0; i < N; i++) {
    int cnt = 0;
    for (int j = 0; j < N; j++)
      cnt += A[i][j];

    for (int j = 0; j < N; j++) {
      deg[i][j][0] = cnt;
      deg[j][i][1] = cnt;
    }
  }

  queue<tuple<int, int, int>> q;
  for (int i = 0; i < N; i++) {
    win[i][i][0] = true;
    los[i][i][1] = true;
    q.push({i, i, 0});
    q.push({i, i, 1});
  }

  while (!q.empty()) {
    auto [a, b, c] = q.front(); q.pop();

    if (c == 0) {
      for (int k = 0; k < N; k++)
        if (A[b][k] && !win[a][k][!c] && !los[a][k][!c]) {
          if (los[a][b][c]) {
            win[a][k][!c] = true;
            q.push({a, k, !c});
          } else if (--deg[a][k][!c] == 0) {
            los[a][k][!c] = true;
            q.push({a, k, !c});
          }
        }
    } else if (c == 1) {
      for (int k = 0; k < N; k++)
        if ((A[a][k] || a == k) && !win[k][b][!c] && !los[k][b][!c]) {
          if (los[a][b][c]) {
            win[k][b][!c] = true;
            nxt[k][b] = a;
            q.push({k, b, !c});
          } else if (--deg[k][b][!c] == 0) {
            los[k][b][!c] = true;
            q.push({k, b, !c});
          }
        }
    }
  }

  for (int i = 0; i < N; i++) {
    int cnt = 0;
    for (int j = 0; j < N; j++)
      cnt += win[i][j][0];

    if (cnt == N)
      return P = i;
  }
  return -1;
}

int nextMove(int R) {
  return P = nxt[P][R];
}

• Subtask 1: 16 / 16
• Subtask 2: 14 / 14
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40