Submission #1307471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307471		lucaskojima	Cop and Robber (BOI14_coprobber)	C++17	60 / 100	514 ms	327680 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;

using state = tuple<int, int, int>;

vector<state> adj_rev[MAX_N][MAX_N][2];
bool win[MAX_N][MAX_N][2];
bool los[MAX_N][MAX_N][2];
bool vis[MAX_N][MAX_N][2];
int deg[MAX_N][MAX_N][2];
pii pos[MAX_N][MAX_N][2];

void dfs(state v) {
  auto [a, b, p] = v;
  vis[a][b][p] = true;

  for (state u : adj_rev[a][b][p]) {
    auto [aa, bb, pp] = u;
    if (vis[aa][bb][pp]) continue;

    if (los[a][b][p]) {
      win[aa][bb][pp] = true;
      pos[aa][bb][pp] = {a, b};
    } else if (--deg[aa][bb][pp] == 0)
      los[aa][bb][pp] = true;
    else
      continue;

    dfs(u);
  }
}

int P;

int start(int N, bool A[MAX_N][MAX_N]) {
  vector<vector<int>> adj(N + 1);
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      if (A[i][j])
        adj[i].push_back(j);

  for (int a = 0; a < N; a++)
    for (int b = 0; b < N; b++)
      for (int p = 0; p < 2; p++) {
        if (p == 0)
          win[a][b][p] = a == b;
        else
          los[a][b][p] = a == b;

        if (win[a][b][p] || los[a][b][p])
          continue;

        if (p == 0) {
          adj_rev[a][b][!p].push_back({a, b, p});
          deg[a][b][p]++;

          for (int k : adj[a]) {
            adj_rev[k][b][!p].push_back({a, b, p});
            deg[a][b][p]++;
          }
        } else {
          for (int k : adj[b]) {
            adj_rev[a][k][!p].push_back({a, b, p});
            deg[a][b][p]++;
          }
        }
      }

  for (int a = 0; a < N; a++)
    for (int b = 0; b < N; b++)
      for (int p = 0; p < 2; p++)
        if ((win[a][b][p] || los[a][b][p]) && !vis[a][b][p])
          dfs({a, b, p});

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

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

int nextMove(int R) {
  return P = pos[P][R][0].first;
}

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