Submission #1269576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269576		rtri	Cop and Robber (BOI14_coprobber)	C++20	16 / 100	23 ms	1860 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> adj;

vector<int> tin, tout, par, vis;
int tick = 0;
void et(int u, int p = -1) {
  if (vis[u])
    return;
  vis[u] = 1;

  tin[u] = tick++;
  par[u] = p;
  for (int v : adj[u])
    if (v != p)
      et(v, u);
  tout[u] = tick++;
}

bool subt(int u, int p) { return tin[p] <= tin[u] && tout[u] <= tout[p]; }

int cop = 0;
int start(int N, bool A[MAX_N][MAX_N]) {
  n = N;

  adj.resize(n);
  for (int u = 0; u < N; u++)
    for (int v = 0; v < N; v++)
      if (A[u][v])
        adj[u].push_back(v);

  tin.resize(n);
  tout.resize(n);
  par.resize(n);
  vis.resize(n);
  et(0);

  return cop;
}

int nextMove(int R) {
  if (R == cop)
    return cop;

  for (int v : adj[cop])
    if (v != par[cop] && (v == R || subt(R, v))) {
      cop = v;
      return v;
    }

  assert(false);
}

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