#include "coprobber.h"
#include "bits/stdc++.h"
using namespace std;
struct node
{
int move, police, thif;
node () {}
node (int move, int police, int thif) : move(move), police(police), thif(thif) {}
};
vector <node> g[2][505][505];
vector <node> t[2][505][505];
bool win[2][505][505];
int deg[2][505][505];
int cur;
node nxt[2][505][505];
int start(int N, bool A[MAX_N][MAX_N])
{
for(int mv = 0; mv <= 1; mv++) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(mv == 0) {
g[mv][i][j].push_back(node(mv ^ 1, i, j));
t[mv ^ 1][i][j].push_back(node(mv, i, j));
// cerr << mv << "-" << i << "-" << j << " " << (mv^1) << "-" << i << "-" << j << endl;
}
for(int k = 0; k < N; k++) {
if(mv == 0 && A[i][k]) {
g[mv][i][j].push_back(node(mv ^ 1, k, j));
t[mv ^ 1][k][j].push_back(node(mv, i, j));
// cerr << mv << "-" << i << "-" << j << " " << (mv^1) << "-" << k << "-" << j << endl;
} else if (mv == 1 && A[j][k]) {
g[mv][i][j].push_back(node(mv ^ 1, i, k));
t[mv ^ 1][i][k].push_back(node(mv, i, j));
// cerr << mv << "-" << i << "-" << j << " " << (mv^1) << "-" << i << "-" << k << endl;
}
}
}
}
}
for(int mv = 0; mv <= 1; mv++) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
deg[mv][i][j] = g[mv][i][j].size();
}
}
}
queue <node> Q;
memset(win, 0, sizeof win);
for(int mv = 0; mv <= 1; mv++) {
for(int i = 0; i < N; i++) {
Q.push(node(mv, i, i));
win[mv][i][i] = 1;
}
}
while(!Q.empty()) {
node n = Q.front();
Q.pop();
for(auto i : t[n.move][n.police][n.thif]) {
if(win[i.move][i.police][i.thif]) continue;
deg[i.move][i.police][i.thif]--;
if(deg[i.move][i.police][i.thif] == 0) {
win[i.move][i.police][i.thif] = 1;
nxt[i.move][i.police][i.thif] = n;
Q.push(i);
// cerr << n.move << " " << n.police << " " << n.thif << " updates " << i.move << " " << i.police << " " << i.thif << endl;
}
else if(i.move == 0) {
win[i.move][i.police][i.thif] = 1;
nxt[i.move][i.police][i.thif] = n;
Q.push(i);
// cerr << n.move << " " << n.police << " " << n.thif << " updates " << i.move << " " << i.police << " " << i.thif << endl;
}
}
}
// cout << nxt[0][0][2].move << " " << nxt[0][0][2].police << " " << nxt[0][0][2].thif << endl;
for(int i = 0; i < N; i++) {
bool sure = true;
for(int j = 0; j < N; j++) {
if(win[0][i][j] == 0) {
sure = false;
}
}
if(sure) {
cur = i;
return i;
}
}
return -1;
}
int nextMove(int R)
{
// cout << "police at: " << cur << " " << " robber at: " << R << endl;
cur = nxt[0][cur][R].police;
return cur;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
24832 KB |
Output is correct |
2 |
Correct |
23 ms |
24832 KB |
Output is correct |
3 |
Correct |
24 ms |
24932 KB |
Output is correct |
4 |
Correct |
469 ms |
81008 KB |
Output is correct |
5 |
Correct |
117 ms |
39988 KB |
Output is correct |
6 |
Correct |
628 ms |
82268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
24832 KB |
Output is correct |
2 |
Correct |
24 ms |
25056 KB |
Output is correct |
3 |
Correct |
644 ms |
113624 KB |
Output is correct |
4 |
Correct |
532 ms |
96760 KB |
Output is correct |
5 |
Correct |
617 ms |
110816 KB |
Output is correct |
6 |
Correct |
557 ms |
106064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
24832 KB |
Output is correct |
2 |
Correct |
23 ms |
24824 KB |
Output is correct |
3 |
Correct |
23 ms |
24960 KB |
Output is correct |
4 |
Correct |
22 ms |
24832 KB |
Output is correct |
5 |
Correct |
23 ms |
24956 KB |
Output is correct |
6 |
Correct |
23 ms |
24832 KB |
Output is correct |
7 |
Correct |
22 ms |
24832 KB |
Output is correct |
8 |
Correct |
23 ms |
24952 KB |
Output is correct |
9 |
Correct |
23 ms |
25216 KB |
Output is correct |
10 |
Correct |
45 ms |
30716 KB |
Output is correct |
11 |
Correct |
125 ms |
57848 KB |
Output is correct |
12 |
Correct |
25 ms |
25472 KB |
Output is correct |
13 |
Correct |
30 ms |
27324 KB |
Output is correct |
14 |
Correct |
66 ms |
39520 KB |
Output is correct |
15 |
Correct |
29 ms |
27392 KB |
Output is correct |
16 |
Correct |
32 ms |
28664 KB |
Output is correct |
17 |
Correct |
137 ms |
64888 KB |
Output is correct |
18 |
Correct |
32 ms |
27512 KB |
Output is correct |
19 |
Correct |
26 ms |
24920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
24836 KB |
Output is correct |
2 |
Correct |
24 ms |
24844 KB |
Output is correct |
3 |
Correct |
23 ms |
24960 KB |
Output is correct |
4 |
Correct |
489 ms |
81144 KB |
Output is correct |
5 |
Correct |
121 ms |
40056 KB |
Output is correct |
6 |
Correct |
645 ms |
82572 KB |
Output is correct |
7 |
Correct |
23 ms |
24832 KB |
Output is correct |
8 |
Correct |
25 ms |
24960 KB |
Output is correct |
9 |
Correct |
649 ms |
113788 KB |
Output is correct |
10 |
Correct |
505 ms |
96632 KB |
Output is correct |
11 |
Correct |
618 ms |
110876 KB |
Output is correct |
12 |
Correct |
548 ms |
106268 KB |
Output is correct |
13 |
Correct |
23 ms |
24824 KB |
Output is correct |
14 |
Correct |
23 ms |
24832 KB |
Output is correct |
15 |
Correct |
22 ms |
24952 KB |
Output is correct |
16 |
Correct |
25 ms |
25336 KB |
Output is correct |
17 |
Correct |
42 ms |
30624 KB |
Output is correct |
18 |
Correct |
123 ms |
57980 KB |
Output is correct |
19 |
Correct |
24 ms |
25464 KB |
Output is correct |
20 |
Correct |
30 ms |
27264 KB |
Output is correct |
21 |
Correct |
66 ms |
39584 KB |
Output is correct |
22 |
Correct |
29 ms |
27364 KB |
Output is correct |
23 |
Correct |
32 ms |
28508 KB |
Output is correct |
24 |
Correct |
130 ms |
64940 KB |
Output is correct |
25 |
Correct |
32 ms |
27520 KB |
Output is correct |
26 |
Correct |
127 ms |
48760 KB |
Output is correct |
27 |
Correct |
444 ms |
88568 KB |
Output is correct |
28 |
Correct |
1250 ms |
219352 KB |
Output is correct |
29 |
Runtime error |
1492 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
30 |
Halted |
0 ms |
0 KB |
- |