Submission #1269577

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

coprobber

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

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

vector<bool> vis;
vector<bool> is_three;
bool has_cycle(int u, int p = -1, int gp = -1, int ggp = -1) {
  // Special handle cycle of length 3
  if (ggp != -1 && u == ggp) {
    is_three[u] = 1;
    is_three[p] = 1;
    is_three[gp] = 1;
    vis[u] = true;
    return false;
  }
  if (is_three[u])
    return false;

  if (vis[u]) {
    return true;
  }
  vis[u] = true;

  for (int v : adj[u])
    if (v != p)
      if (has_cycle(v, u, p, gp))
        return true;
  return false;
}

vector<int> tin, tout, par;
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);

  is_three.resize(n);
  vis.resize(n);
  if (has_cycle(0))
    return -1;

  tin.resize(n);
  tout.resize(n);
  par.resize(n);
  fill(vis.begin(), vis.end(), false);
  et(0);

  return 0;
}

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 cop;
    }

  cop = par[cop];
  return cop;
}

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