#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#include "coprobber.h"
#endif
#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#endif
struct wow {
int cop,robber,turn;
};
vector<vector<int>> g;
const int nmax = 505;
wow last[nmax][nmax][2];
#ifdef LOCAL
const int MAX_N = 500;
#endif
int dp[nmax][nmax][2],nrAdjacent[nmax][nmax],copPosition;
bool situation[nmax][nmax][2];
int start(int n, bool a[MAX_N][MAX_N]) {
queue<wow> q;
g.resize(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 1) {
g[i].push_back(j);
}
}
}
///dp[i][j][turn], turn = 0 -> cops turn, 1->robber's turn
///dp is 1 if from this position cop can catch robber, 0 otherwise
///if it's 1 and turn = 0, then move[i][j] should contain a possible move for the cop
///that he can make so he can get to the robber.
for (int i = 0; i < n; i++) {
dp[i][i][0] = dp[i][i][1] = 1;
q.push({i,i,0});
q.push({i,i,1});
}
///queue just contains values that have been turned to 1
while(!q.empty()) {
int cop = q.front().cop;
int robber = q.front().robber;
int turn = q.front().turn;
q.pop();
auto change = [&](int xcop, int xrobber, int xturn) {
if (dp[xcop][xrobber][xturn] == 0) {
dp[xcop][xrobber][xturn] = 1;
last[xcop][xrobber][xturn] = {cop, robber,turn};
q.push({xcop,xrobber,xturn});
}
};
if (turn == 1) { // robber's turn, this leads to the samae position in 0, as well as all neighbours of the cop in 0.
for (auto k : g[cop]) {
change(k,robber,0);
}
change(cop,robber,0);///cop can wait and get lead to this situation.
} else {
///any neighbours 1's need to have all of their robber neighbours taken
///we take a robber move from a certain neighbour to get here
for (auto k : g[robber]) {
nrAdjacent[cop][k]++;///nr of adjacent cop move nodes that are 1 next to this robber move
if (nrAdjacent[cop][k] == g[k].size()) {
change(cop, k, 1);///this robber turn position is taken
}
}
}
}
///we want to find a corner where all dp[A][x][0] = 1
for (int i = 0; i < n; i++) {
bool any0 = false;
for (int j = 0; j < n; j++) {
if (dp[i][j][0] == 0) {
any0 = true;
break;
}
}
if (!any0) {
copPosition = i;
return i;
}
}
return -1;
}
int nextMove(int R) {
return copPosition = last[copPosition][R][0].cop;///cop where we came from. since this is a 0 it came from 1 so the cop changed.
}
#ifdef LOCAL
bool a[MAX_N][MAX_N];
int main() {
int n;
in >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
in >> a[i][j];
}
}
start(n , a);
nextMove(3);
}
#endif
Compilation message
coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:73:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if (nrAdjacent[cop][k] == g[k].size()) {
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
0 ms |
328 KB |
Output is correct |
4 |
Correct |
70 ms |
10688 KB |
Output is correct |
5 |
Correct |
14 ms |
4680 KB |
Output is correct |
6 |
Correct |
61 ms |
10976 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
328 KB |
Output is correct |
2 |
Correct |
0 ms |
456 KB |
Output is correct |
3 |
Correct |
52 ms |
10492 KB |
Output is correct |
4 |
Correct |
52 ms |
10644 KB |
Output is correct |
5 |
Correct |
54 ms |
10340 KB |
Output is correct |
6 |
Correct |
52 ms |
10412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
328 KB |
Output is correct |
2 |
Correct |
0 ms |
328 KB |
Output is correct |
3 |
Correct |
0 ms |
328 KB |
Output is correct |
4 |
Correct |
0 ms |
328 KB |
Output is correct |
5 |
Correct |
1 ms |
456 KB |
Output is correct |
6 |
Correct |
0 ms |
328 KB |
Output is correct |
7 |
Correct |
0 ms |
328 KB |
Output is correct |
8 |
Correct |
1 ms |
328 KB |
Output is correct |
9 |
Correct |
0 ms |
456 KB |
Output is correct |
10 |
Correct |
2 ms |
1480 KB |
Output is correct |
11 |
Correct |
3 ms |
1608 KB |
Output is correct |
12 |
Correct |
1 ms |
584 KB |
Output is correct |
13 |
Correct |
2 ms |
1224 KB |
Output is correct |
14 |
Correct |
3 ms |
1608 KB |
Output is correct |
15 |
Correct |
1 ms |
968 KB |
Output is correct |
16 |
Correct |
1 ms |
968 KB |
Output is correct |
17 |
Correct |
6 ms |
1876 KB |
Output is correct |
18 |
Correct |
1 ms |
1352 KB |
Output is correct |
19 |
Correct |
0 ms |
328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
0 ms |
328 KB |
Output is correct |
4 |
Correct |
70 ms |
10688 KB |
Output is correct |
5 |
Correct |
14 ms |
4680 KB |
Output is correct |
6 |
Correct |
61 ms |
10976 KB |
Output is correct |
7 |
Correct |
0 ms |
328 KB |
Output is correct |
8 |
Correct |
0 ms |
456 KB |
Output is correct |
9 |
Correct |
52 ms |
10492 KB |
Output is correct |
10 |
Correct |
52 ms |
10644 KB |
Output is correct |
11 |
Correct |
54 ms |
10340 KB |
Output is correct |
12 |
Correct |
52 ms |
10412 KB |
Output is correct |
13 |
Correct |
0 ms |
328 KB |
Output is correct |
14 |
Correct |
0 ms |
328 KB |
Output is correct |
15 |
Correct |
0 ms |
328 KB |
Output is correct |
16 |
Correct |
0 ms |
328 KB |
Output is correct |
17 |
Correct |
1 ms |
456 KB |
Output is correct |
18 |
Correct |
0 ms |
328 KB |
Output is correct |
19 |
Correct |
0 ms |
328 KB |
Output is correct |
20 |
Correct |
1 ms |
328 KB |
Output is correct |
21 |
Correct |
0 ms |
456 KB |
Output is correct |
22 |
Correct |
2 ms |
1480 KB |
Output is correct |
23 |
Correct |
3 ms |
1608 KB |
Output is correct |
24 |
Correct |
1 ms |
584 KB |
Output is correct |
25 |
Correct |
2 ms |
1224 KB |
Output is correct |
26 |
Correct |
3 ms |
1608 KB |
Output is correct |
27 |
Correct |
1 ms |
968 KB |
Output is correct |
28 |
Correct |
1 ms |
968 KB |
Output is correct |
29 |
Correct |
6 ms |
1876 KB |
Output is correct |
30 |
Correct |
1 ms |
1352 KB |
Output is correct |
31 |
Correct |
0 ms |
328 KB |
Output is correct |
32 |
Correct |
0 ms |
328 KB |
Output is correct |
33 |
Correct |
0 ms |
328 KB |
Output is correct |
34 |
Correct |
0 ms |
328 KB |
Output is correct |
35 |
Correct |
54 ms |
10664 KB |
Output is correct |
36 |
Correct |
21 ms |
4648 KB |
Output is correct |
37 |
Correct |
61 ms |
10900 KB |
Output is correct |
38 |
Correct |
0 ms |
328 KB |
Output is correct |
39 |
Correct |
1 ms |
456 KB |
Output is correct |
40 |
Correct |
53 ms |
10540 KB |
Output is correct |
41 |
Correct |
68 ms |
10692 KB |
Output is correct |
42 |
Correct |
50 ms |
10364 KB |
Output is correct |
43 |
Correct |
69 ms |
10504 KB |
Output is correct |
44 |
Correct |
0 ms |
328 KB |
Output is correct |
45 |
Correct |
1 ms |
328 KB |
Output is correct |
46 |
Correct |
0 ms |
328 KB |
Output is correct |
47 |
Correct |
1 ms |
456 KB |
Output is correct |
48 |
Correct |
2 ms |
1480 KB |
Output is correct |
49 |
Correct |
3 ms |
1608 KB |
Output is correct |
50 |
Correct |
1 ms |
584 KB |
Output is correct |
51 |
Correct |
2 ms |
1224 KB |
Output is correct |
52 |
Correct |
2 ms |
1608 KB |
Output is correct |
53 |
Correct |
1 ms |
968 KB |
Output is correct |
54 |
Correct |
1 ms |
968 KB |
Output is correct |
55 |
Correct |
5 ms |
1872 KB |
Output is correct |
56 |
Correct |
1 ms |
1352 KB |
Output is correct |
57 |
Correct |
4 ms |
3016 KB |
Output is correct |
58 |
Correct |
15 ms |
6736 KB |
Output is correct |
59 |
Correct |
20 ms |
9296 KB |
Output is correct |
60 |
Correct |
713 ms |
14512 KB |
Output is correct |
61 |
Correct |
88 ms |
9964 KB |
Output is correct |
62 |
Correct |
74 ms |
10880 KB |
Output is correct |
63 |
Correct |
463 ms |
13156 KB |
Output is correct |
64 |
Correct |
47 ms |
10168 KB |
Output is correct |
65 |
Correct |
525 ms |
14256 KB |
Output is correct |
66 |
Correct |
84 ms |
10832 KB |
Output is correct |
67 |
Correct |
259 ms |
12704 KB |
Output is correct |
68 |
Correct |
87 ms |
9960 KB |
Output is correct |
69 |
Correct |
0 ms |
328 KB |
Output is correct |