Submission #554668

#	Time	Username	Problem	Language	Result	Execution time	Memory
554668		ollel	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	40 ms	1832 KiB

coprobber

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

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef long long ll;
typedef pair<int,int> pii;

#include "coprobber.h"

int n;
vvi adj;
vector<set<int>> adj_set;
vector<set<int>> in_cycle;

int cop = 0;

void cycle_dfs(int x, int camefrom, vi & depth, vi & parent, vi & backDepth) { // highest depth of back edge, lowest down, max length of cycle
  backDepth[x] = depth[x];
  for (auto & j : adj[x]) {
    if (j == camefrom) continue;
    if (depth[j] == -1) {
      depth[j] = depth[x] + 1;
      parent[j] = x;
      cycle_dfs(j, x, depth, parent, backDepth);
    }
    else {
      backDepth[x] = min(backDepth[x], depth[j]);
    }
  }
}

int start(int N, bool A[MAX_N][MAX_N])
{
  n = N;
  adj.resize(n);
  rep(i,0,n) {
    rep(j,0,n) {
      if (A[i][j]) adj[i].pb(j);
    }
  }

  vi depth(n, -1);
  vi backDepth(n, -1), parent(n, -1);

  depth[0] = 0;
  cycle_dfs(0, -1, depth, parent, backDepth);

  in_cycle.resize(n);

  rep(i,0,n) {
    int node = i, cycle = 1, back = backDepth[i];
    in_cycle[i].insert(i);
    while (depth[node] > back) {
      cycle++;
      back = min(back, backDepth[node]);
      node = parent[node];
      in_cycle[i].insert(node);
      if (cycle > 4) return -1;
    }
  }
  rep(i,0,n) for (auto & j : in_cycle[i]) for (auto & k : in_cycle[i]) in_cycle[j].insert(k);
  // rep(i,0,n) {
  //   for (auto j : in_cycle[i]) cout << j << " ";
  //   cout << endl;
  // }


  adj_set.resize(n);
  rep(i,0,n) for (auto & j : adj[i]) adj_set[i].insert(j);

  return 0;
}

int nextMove(int robber)
{
  if (adj_set[cop].find(robber) != adj_set[cop].end()) {
    return robber;
  }

  if (in_cycle[cop].find(robber) != in_cycle[cop].end()) {
    return cop;
  }

  vi back(n, -1);
  back[cop] = 0;
  queue<int> q; q.push(cop);
  while (!q.empty()) {
    int x = q.front(); q.pop();
    for (auto j : adj[x]) {
      if (back[j] != -1) continue;
      back[j] = x;
      q.push(j);
    }
  }

  int y = robber;
  while (back[y] != cop) y = back[y];
  cop = y;
  return y;
}
//
// int main() {
//   int n = 5;
//   vector<vector<bool>> a = {{0, 1, 0, 1, 1}, {1, 0, 1, 0, 0}, {0, 1, 0, 1, 0}, {1, 0, 1, 0, 0}, {1, 0, 0, 0, 0}};
//   start(n, a);
// }

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