#include "coprobber.h"
int P[MAX_N][MAX_N], Q[MAX_N][MAX_N];
int E[MAX_N][MAX_N];
int C2[MAX_N][MAX_N], n;
int Deg[MAX_N];
int Q1[MAX_N*MAX_N], Q2[MAX_N*MAX_N], t1, t2, h1, h2;
int node;
void UDT1(int x, int y)
{
int i;
for (i = 0; i < n; i++){
if (E[y][i]){
C2[x][i]++;
if (C2[x][i] == Deg[i]){
Q[x][i] = P[x][y];
Q2[++t2] = (x << 9) + i;
}
}
}
}
void UDT2(int x, int y)
{
int i;
for (i = 0; i < n; i++){
if (E[x][i] && !P[i][y]){
Q1[++t1] = (i << 9) + y;
P[i][y] = Q[x][y] + 1;
}
}
if (!P[x][y]){
Q1[++t1] = (x << 9) + y;
P[x][y] = Q[x][y] + 1;
}
}
int start(int N, bool A[MAX_N][MAX_N])
{
n = N;
int i, j, k;
for (i = 0; i < n; i++){
for (j = 0; j < n; j++){
E[i][j] = A[i][j];
if (E[i][j])Deg[i]++;
}
}
for (i = 0; i < n; i++){
P[i][i] = 1;
UDT1(i, i);
for (j = 0; j < n; j++){
if (A[i][j]){
P[i][j] = 1;
UDT1(i, j);
}
}
}
while (h2<t2){
while (h2<t2){
++h2;
UDT2(Q2[h2] >> 9, Q2[h2] & 511);
}
while (h1<t1){
++h1;
UDT1(Q1[h1] >> 9, Q1[h1] & 511);
}
}
for (i = 0; i < n; i++){
for (j = 0; j < n; j++){
if (!P[i][j])break;
}
if (j == n)break;
}
if (i == n)return -1;
node = i;
return i;
}
int nextMove(int R)
{
if (E[node][R] || node == R){
return R;
}
int i, M = 9999999, x;
for (i = 0; i < n; i++){
if ((E[node][i] || i == node) && Q[i][R] && M > Q[i][R]){
M = Q[i][R];
x = i;
}
}
node = x;
return x;
}
Compilation message
coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:42:12: warning: unused variable 'k' [-Wunused-variable]
int i, j, k;
^
coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:92:7: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
node = x;
~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
356 KB |
Output is correct |
4 |
Correct |
244 ms |
7684 KB |
Output is correct |
5 |
Correct |
38 ms |
3232 KB |
Output is correct |
6 |
Correct |
280 ms |
7384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
249 ms |
7416 KB |
Output is correct |
4 |
Correct |
252 ms |
7660 KB |
Output is correct |
5 |
Correct |
244 ms |
7224 KB |
Output is correct |
6 |
Correct |
252 ms |
7516 KB |
Output is correct |
# |
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 |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
1124 KB |
Output is correct |
11 |
Correct |
6 ms |
1152 KB |
Output is correct |
12 |
Correct |
2 ms |
640 KB |
Output is correct |
13 |
Correct |
3 ms |
1024 KB |
Output is correct |
14 |
Correct |
5 ms |
1200 KB |
Output is correct |
15 |
Correct |
3 ms |
896 KB |
Output is correct |
16 |
Correct |
3 ms |
816 KB |
Output is correct |
17 |
Correct |
9 ms |
1408 KB |
Output is correct |
18 |
Correct |
3 ms |
1152 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
432 KB |
Output is correct |
3 |
Correct |
2 ms |
540 KB |
Output is correct |
4 |
Correct |
251 ms |
7672 KB |
Output is correct |
5 |
Correct |
43 ms |
3292 KB |
Output is correct |
6 |
Correct |
299 ms |
7460 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
512 KB |
Output is correct |
9 |
Correct |
257 ms |
7352 KB |
Output is correct |
10 |
Correct |
251 ms |
7644 KB |
Output is correct |
11 |
Correct |
259 ms |
7208 KB |
Output is correct |
12 |
Correct |
263 ms |
7448 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
512 KB |
Output is correct |
17 |
Correct |
3 ms |
1152 KB |
Output is correct |
18 |
Correct |
6 ms |
1124 KB |
Output is correct |
19 |
Correct |
2 ms |
640 KB |
Output is correct |
20 |
Correct |
3 ms |
1024 KB |
Output is correct |
21 |
Correct |
5 ms |
1152 KB |
Output is correct |
22 |
Correct |
3 ms |
896 KB |
Output is correct |
23 |
Correct |
3 ms |
896 KB |
Output is correct |
24 |
Correct |
9 ms |
1452 KB |
Output is correct |
25 |
Correct |
3 ms |
1152 KB |
Output is correct |
26 |
Correct |
7 ms |
2048 KB |
Output is correct |
27 |
Correct |
20 ms |
3648 KB |
Output is correct |
28 |
Correct |
26 ms |
4480 KB |
Output is correct |
29 |
Correct |
327 ms |
6396 KB |
Output is correct |
30 |
Correct |
188 ms |
4088 KB |
Output is correct |
31 |
Correct |
155 ms |
4448 KB |
Output is correct |
32 |
Correct |
625 ms |
6944 KB |
Output is correct |
33 |
Correct |
104 ms |
4816 KB |
Output is correct |
34 |
Correct |
934 ms |
6736 KB |
Output is correct |
35 |
Correct |
283 ms |
6944 KB |
Output is correct |
36 |
Correct |
852 ms |
7188 KB |
Output is correct |
37 |
Correct |
275 ms |
5272 KB |
Output is correct |
38 |
Correct |
2 ms |
384 KB |
Output is correct |