| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1125832 | mingga | Cop and Robber (BOI14_coprobber) | C++17 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
#include "coprobber.h"
using namespace std;
#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
// #define int long long
const int MOD = 1e9 + 7;
const int inf = 2e9;
const int N = 505;
bool w[N][N];
bool f[N][N][2];
int vis[N][N][2], opt[N][N];
vector<int> g[N];
int pre;
bool calc(int u, int v, int steps) {
if(u == v) {
return f[u][v][steps] = 1;
}
if(vis[u][v][steps]) return f[u][v][steps];
vis[u][v][steps] = 1;
if(steps & 1) {
bool ans = 0;
for(int x : g[u]) {
if(vis[x][v][0] == 1) {
continue;
}
if(calc(x, v, 0)) opt[u][v] = x;
ans = ans | calc(x, v, 0);
}
if(vis[u][v][0] != 1) ans = ans | calc(u, v, 0);
if(calc(u, v, 0)) opt[u][v] = u;
vis[u][v][steps] = 2;
return f[u][v][steps] = ans;
} else {
bool ans = 1;
for(int x : g[v]) {
if(vis[u][x][1] == 1) return 0;
ans = ans & calc(u, x, 1);
}
vis[u][v][steps] = 2;
return f[u][v][steps] = ans;
}
}
int start(int n, bool a[N][N]) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
w[i][j] = a[i][j];
if(w[i][j]) {
g[i].pb(j);
}
}
}
int ans = -1;
for(int i = 0; i < n; i++) {
bool cur = 1;
for(int j = 0; j < n; j++) {
cur = cur & calc(i, j, 1);
}
if(cur) {
pre = i;
return i;
}
}
return ans;
}
int nextMove(int x) {
pre = opt[pre][x];
return pre;
}