#include <bits/stdc++.h>
using namespace std;
const size_t M = 512;
int n;
bool G[M][M];
bool vis[2][M][M], win[2][M][M], lose[2][M][M];
int opt[2][M][M], deg[2][M][M], vertex;
void dfs(bool t, int u, int v)
{
vis[t][u][v] = true;
if(t) // robber
{
for(int u1 = 0; u1 < n; u1++) if(G[u1][u] and not vis[0][u1][v])
{
if(lose[1][u][v])
win[0][u1][v] = true, opt[0][u1][v] = u;
else if(--deg[0][u1][v] == 0)
lose[0][u1][v] = true;
else
continue;
dfs(0, u1, v);
}
}
else // cop
{
for(int v1 = 0; v1 < n; v1++) if(G[v1][v] and not vis[1][u][v1])
{
if(lose[0][u][v])
win[1][u][v1] = true, opt[1][u][v1] = v;
else if(--deg[1][u][v1] == 0)
lose[1][u][v1] = true;
else
continue;
dfs(1, u, v1);
}
}
}
int start(int _n, bool _G[500][500])
{
n = _n;
for(int u = 0; u < n; u++)
for(int v = 0; v < n; v++)
G[u][v] = _G[u][v], opt[0][u][v] = opt[1][u][v] = -1;
for(int u = 0; u < n; u++)
win[0][u][u] = lose[1][u][u] = true;
for(int u = 0; u < n; u++)
if(not vis[1][u][u])
dfs(1, u, u);
for(int u = 0; u < n; u++)
{
bool all = true;
for(int v = 0; v < n; v++)
if(not win[0][u][v])
all = false;
if(all)
return vertex = u;
}
return -1;
}
int nextMove(int r)
{
return vertex = opt[0][vertex][r];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Incorrect |
1 ms |
492 KB |
Cop can catch the robber, but start() returned -1 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Cop can catch the robber, but start() returned -1 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Incorrect |
1 ms |
492 KB |
Cop can catch the robber, but start() returned -1 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Incorrect |
1 ms |
492 KB |
Cop can catch the robber, but start() returned -1 |
4 |
Halted |
0 ms |
0 KB |
- |