#include "coprobber.h"
#include <tuple>
#include <array>
#include <queue>
#include <string.h>
int N, G[MAX_N][MAX_N][2], C[MAX_N][MAX_N][2], deg[MAX_N], at;
bool (*A)[MAX_N];
int start(int N, bool A[MAX_N][MAX_N])
{
::N = N, ::A = A;
//memset(G, -1, sizeof G);
std::queue<std::tuple<int, int, int, int>> q;
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) deg[i] += A[i][j], G[i][j][0] = G[i][j][1] = 1;
for (int i = 0; i < N; ++i) G[i][i][0] = G[i][i][1] = 0, q.emplace(i, i, 0, 0), q.emplace(i, i, 1, 0);
for (; q.size(); )
{
auto [u, v, t, g] = q.front();
q.pop();
if (t) /* robber, was cop */
{
for (auto k = 0; k < N; ++k)
{
if (!A[u][k]) continue;
if (G[k][v][!t] && !g)
q.emplace(k, v, !t, G[k][v][!t] = 0);
}
}
else /* was robber */
{
for (auto k = 0; k < N; ++k)
{
if (!A[v][k]) continue;
if (!g)
{
if (++C[u][k][0] == deg[k])
{
q.emplace(u, k, !t, G[u][k][!t] = 0);
}
}
}
}
}
for (int i = 0; i < N; ++i)
{
int win = 0;
for (int j = 0; j < N; ++j)
win += !G[i][j][0];
if (win == N) return at = i;
}
return -1;
}
int nextMove(int R)
{
if (!G[at][R][1]) return at;
for (int j = 0; j < N; ++j)
if (A[at][j] && !G[j][R][1]) return j;
return -1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Incorrect |
1 ms |
4440 KB |
the situation repeated |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
4440 KB |
Cop can catch the robber, but start() returned -1 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Incorrect |
1 ms |
4440 KB |
the situation repeated |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Incorrect |
1 ms |
4440 KB |
the situation repeated |
4 |
Halted |
0 ms |
0 KB |
- |