#include <bits/stdc++.h>
using namespace std;
const size_t M = 512;
int n = -1;
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], gdeg[M], vertex = -1;
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++)
for(int v = 0; v < n; v++)
gdeg[u] += G[u][v];
for(int u = 0; u < n; u++)
for(int v = 0; v < n; v++)
deg[0][u][v] = gdeg[u] + 1, deg[1][u][v] = gdeg[v];
for(int u = 0; u < n; u++)
win[0][u][u] = lose[1][u][u] = true;
vector<tuple<int, int, int>> tovis;
for(auto t : {0, 1})
for(int u = 0; u < n; u++)
if(not vis[t][u][u])
vis[t][u][u] = true, tovis.emplace_back(t, u, u);
while(not tovis.empty())
{
auto [t, u, v] = tovis.back(); tovis.pop_back();
if(t)
{
for(int u1 = 0; u1 < n; u1++) if((u1 == u or G[u][u1]) 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;
vis[0][u1][v] = true;
tovis.emplace_back(0, u1, v);
}
}
else // cop
{
for(int v1 = 0; v1 < n; v1++) if(G[v][v1] 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;
vis[1][u][v1] = true;
tovis.emplace_back(1, u, v1);
}
}
}
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];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
828 ms |
7148 KB |
Output is correct |
5 |
Correct |
103 ms |
3564 KB |
Output is correct |
6 |
Correct |
872 ms |
7020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
816 ms |
6852 KB |
Output is correct |
4 |
Correct |
837 ms |
7148 KB |
Output is correct |
5 |
Correct |
765 ms |
6764 KB |
Output is correct |
6 |
Correct |
849 ms |
6892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
620 KB |
Output is correct |
10 |
Correct |
3 ms |
1516 KB |
Output is correct |
11 |
Correct |
5 ms |
1516 KB |
Output is correct |
12 |
Correct |
1 ms |
748 KB |
Output is correct |
13 |
Correct |
2 ms |
1260 KB |
Output is correct |
14 |
Correct |
6 ms |
1516 KB |
Output is correct |
15 |
Correct |
3 ms |
1004 KB |
Output is correct |
16 |
Correct |
3 ms |
1004 KB |
Output is correct |
17 |
Correct |
12 ms |
1644 KB |
Output is correct |
18 |
Correct |
2 ms |
1516 KB |
Output is correct |
19 |
Correct |
0 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
828 ms |
7148 KB |
Output is correct |
5 |
Correct |
103 ms |
3564 KB |
Output is correct |
6 |
Correct |
872 ms |
7020 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
816 ms |
6852 KB |
Output is correct |
10 |
Correct |
837 ms |
7148 KB |
Output is correct |
11 |
Correct |
765 ms |
6764 KB |
Output is correct |
12 |
Correct |
849 ms |
6892 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
492 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
1 ms |
620 KB |
Output is correct |
22 |
Correct |
3 ms |
1516 KB |
Output is correct |
23 |
Correct |
5 ms |
1516 KB |
Output is correct |
24 |
Correct |
1 ms |
748 KB |
Output is correct |
25 |
Correct |
2 ms |
1260 KB |
Output is correct |
26 |
Correct |
6 ms |
1516 KB |
Output is correct |
27 |
Correct |
3 ms |
1004 KB |
Output is correct |
28 |
Correct |
3 ms |
1004 KB |
Output is correct |
29 |
Correct |
12 ms |
1644 KB |
Output is correct |
30 |
Correct |
2 ms |
1516 KB |
Output is correct |
31 |
Correct |
0 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
492 KB |
Output is correct |
34 |
Correct |
1 ms |
492 KB |
Output is correct |
35 |
Correct |
833 ms |
7056 KB |
Output is correct |
36 |
Correct |
105 ms |
3564 KB |
Output is correct |
37 |
Correct |
871 ms |
7020 KB |
Output is correct |
38 |
Correct |
1 ms |
492 KB |
Output is correct |
39 |
Correct |
1 ms |
492 KB |
Output is correct |
40 |
Correct |
820 ms |
6864 KB |
Output is correct |
41 |
Correct |
832 ms |
7148 KB |
Output is correct |
42 |
Correct |
765 ms |
6796 KB |
Output is correct |
43 |
Correct |
844 ms |
7020 KB |
Output is correct |
44 |
Correct |
0 ms |
364 KB |
Output is correct |
45 |
Correct |
1 ms |
492 KB |
Output is correct |
46 |
Correct |
1 ms |
492 KB |
Output is correct |
47 |
Correct |
1 ms |
620 KB |
Output is correct |
48 |
Correct |
2 ms |
1516 KB |
Output is correct |
49 |
Correct |
5 ms |
1516 KB |
Output is correct |
50 |
Correct |
1 ms |
748 KB |
Output is correct |
51 |
Correct |
2 ms |
1132 KB |
Output is correct |
52 |
Correct |
7 ms |
1516 KB |
Output is correct |
53 |
Correct |
3 ms |
1004 KB |
Output is correct |
54 |
Correct |
3 ms |
1004 KB |
Output is correct |
55 |
Correct |
12 ms |
1644 KB |
Output is correct |
56 |
Correct |
2 ms |
1516 KB |
Output is correct |
57 |
Correct |
7 ms |
2540 KB |
Output is correct |
58 |
Correct |
23 ms |
4844 KB |
Output is correct |
59 |
Correct |
49 ms |
5868 KB |
Output is correct |
60 |
Correct |
1168 ms |
7020 KB |
Output is correct |
61 |
Correct |
180 ms |
5424 KB |
Output is correct |
62 |
Correct |
173 ms |
5868 KB |
Output is correct |
63 |
Correct |
1044 ms |
7020 KB |
Output is correct |
64 |
Correct |
216 ms |
5868 KB |
Output is correct |
65 |
Correct |
1076 ms |
7148 KB |
Output is correct |
66 |
Correct |
787 ms |
6876 KB |
Output is correct |
67 |
Correct |
1022 ms |
7020 KB |
Output is correct |
68 |
Correct |
499 ms |
5868 KB |
Output is correct |
69 |
Correct |
1 ms |
364 KB |
Output is correct |