This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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);
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++;
node = parent[node];
back = min(back, backDepth[node]);
in_cycle[i].insert(node);
if (cycle > 4) return -1;
}
}
rep(i,0,n) for (auto & j : in_cycle[i]) in_cycle[j].insert(i);
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];
return y;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |