#include "coprobber.h"
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int indeg[500][500][2];
queue<int> qx, qy, qd;
bool vis[500][500][2];
int nxt[500][500];
int pos;
int start(int N, bool A[MAX_N][MAX_N])
{
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
if (i == j) continue;
indeg[i][j][1] = count(A[j], A[j] + N, true);
indeg[i][j][0] = min((int)count(A[i], A[i] + N, true), 1);
}
}
for (int i = 0; i < N; i++){
for (int k = 0; k < 2; k++){
qx.push(i);
qy.push(i);
qd.push(k);
vis[i][i][k] = 1;
}
}
while (!qx.empty()){
int xf = qx.front();
int yf = qy.front();
int df = qd.front();
qx.pop(), qy.pop(), qd.pop();
if (df == 1){
for (int i = 0; i < N; i++){
if (A[xf][i] && !vis[i][yf][0]){
indeg[i][yf][0]--;
if (indeg[i][yf][0] == 0){
qx.push(i);
qy.push(yf);
qd.push(0);
nxt[i][yf] = xf;
vis[i][yf][0] = 1;
}
}
}
}
else{
for (int i = 0; i < N; i++){
if (A[yf][i] &&!vis[xf][i][1]){
indeg[xf][i][1]--;
if (indeg[xf][i][1] == 0){
qx.push(xf);
qy.push(i);
qd.push(1);
vis[xf][i][1] = 1;
}
}
}
}
}
for (int i = 0; i < N; i++){
int fnd = 0;
for (int j = 0; j < N; j++){
if (!vis[i][j][0]){
fnd = 1;
break;
}
}
if (!fnd) return pos = i;
}
return -1;
}
int nextMove(int R)
{
return pos = nxt[pos][R];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
754 ms |
5148 KB |
Output is correct |
5 |
Correct |
94 ms |
2680 KB |
Output is correct |
6 |
Correct |
802 ms |
5568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
384 KB |
Cop can catch the robber, but start() returned -1 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Incorrect |
2 ms |
384 KB |
Cop can catch the robber, but start() returned -1 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
750 ms |
5148 KB |
Output is correct |
5 |
Correct |
93 ms |
2688 KB |
Output is correct |
6 |
Correct |
834 ms |
5456 KB |
Output is correct |
7 |
Incorrect |
2 ms |
384 KB |
Cop can catch the robber, but start() returned -1 |
8 |
Halted |
0 ms |
0 KB |
- |