#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
#define MAX_N 500
// modify the following functions
// you can define global variables and functions
bool dp[MAX_N][MAX_N][2];
bool used[MAX_N][MAX_N][2];
vector <vector <int> > grev(MAX_N);
int deg[MAX_N][MAX_N][2];
int cur;
void dfs(int v, int u, int ind){
used[v][u][ind] = true;
if(ind == 0){
for(int to : grev[u]){
if(used[v][to][ind ^ 1]) continue;
if(dp[v][u][ind]){
deg[v][to][ind ^ 1]--;
if(deg[v][to][ind ^ 1] == 0) dp[v][to][ind ^ 1] = 0, dfs(v, to, ind ^ 1);
}
if(!dp[v][u][ind]) {
dp[v][to][ind ^ 1] = true;
dfs(v, to, ind ^ 1);
}
}
}
else{
// grev[v].pb(v);
for(int to : grev[v]){
if(used[to][u][ind ^ 1]) continue;
if(dp[v][u][ind]){
deg[to][u][ind ^ 1]--;
if(deg[to][u][ind ^ 1] == 0) dp[to][u][ind ^ 1] = 0, dfs(to, u, ind ^ 1);
}
if(!dp[v][u][ind]){
dp[to][u][ind ^ 1] = true;
dfs(to, u, ind ^ 1);
}
}
if(used[v][u][ind ^ 1])return;
if(dp[v][u][ind ^ 1]){
deg[v][u][ind ^ 1]--;
if(deg[v][u][ind ^ 1] == 0) dp[v][u][ind ^ 1] = 0, dfs(v, u, ind ^ 1);
}
else{
dp[v][u][ind ^ 1] = 1;
dfs(v, u, ind ^ 1);
}
//grev[v].pop_back();
}
}
int start(int N, bool A[MAX_N][MAX_N]) {
int n = N;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(A[i][j]) grev[j].pb(i);
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
deg[i][j][0] = grev[j].size();
deg[i][j][1] = grev[i].size() + 1;
}
}
for(int i = 0; i < n; i++){
dp[i][i][0] = 1;
dp[i][i][1] = 0;
}
for(int i = 0; i < n; i++){
dfs(i, i, 0);
dfs(i, i, 1);
}
int ans = -1;
for(int i = 0; i < n; i++){
bool ind = true;
for(int j= 0; j < n; j++){
if(!dp[i][j][0]){
ind = false;
break;
}
}
if(ind) {
cur = i;
return i;
}
}
return -1;
}
int nextMove(int R) {
for(int to : grev[cur]){
if(dp[cur][R][1] == 0){
return cur;
}
if(dp[to][R][1] == 0) {
cur = to;
return cur;
}
}
}
Compilation message
coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:89:9: warning: unused variable 'ans' [-Wunused-variable]
89 | int ans = -1;
| ^~~
coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:116:1: warning: control reaches end of non-void function [-Wreturn-type]
116 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Incorrect |
1 ms |
336 KB |
Cop can catch the robber, but start() returned -1 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
336 KB |
Cop can catch the robber, but start() returned -1 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Incorrect |
0 ms |
336 KB |
Cop can catch the robber, but start() returned -1 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Incorrect |
1 ms |
336 KB |
Cop can catch the robber, but start() returned -1 |
4 |
Halted |
0 ms |
0 KB |
- |