#include "game.h"
#include <stdlib.h>
const int N = 300000;
int *ej[N], eo[N], *fi[N], fo[N], ll[N], rr[N], n, k;
void append(int **ej, int *eo, int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
void init(int n_, int k_) {
n = n_, k = k_;
for (int i = 0; i < n; i++) {
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
fi[i] = (int *) malloc(2 * sizeof *fi[i]);
}
for (int i = 0; i < n; i++)
if (i < k)
ll[i] = rr[i] = i;
else
ll[i] = -1, rr[i] = k;
}
int dfs1(int i, int l) {
int o;
if (ll[i] >= l)
return 0;
ll[i] = l;
if (ll[i] > rr[i] || ll[i] == rr[i] && i >= k)
return 1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (dfs1(j, l))
return 1;
}
return 0;
}
int dfs2(int j, int r) {
int o;
if (rr[j] <= r)
return 0;
rr[j] = r;
if (ll[j] > rr[j] || ll[j] == rr[j] && j >= k)
return 1;
for (o = fo[j]; o--; ) {
int i = fi[j][o];
if (dfs2(i, r))
return 1;
}
return 0;
}
int add_teleporter(int i, int j) {
if (i == j)
return i < k;
append(ej, eo, i, j), append(fi, fo, j, i);
return dfs1(j, ll[i]) || dfs2(i, rr[j]);
}
Compilation message
game.cpp: In function 'void append(int**, int*, int, int)':
game.cpp:10:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
10 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
game.cpp: In function 'int dfs1(int, int)':
game.cpp:33:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
33 | if (ll[i] > rr[i] || ll[i] == rr[i] && i >= k)
| ~~~~~~~~~~~~~~~^~~~~~~~~
game.cpp: In function 'int dfs2(int, int)':
game.cpp:48:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
48 | if (ll[j] > rr[j] || ll[j] == rr[j] && j >= k)
| ~~~~~~~~~~~~~~~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
0 ms |
208 KB |
Output is correct |
| 10 |
Correct |
0 ms |
208 KB |
Output is correct |
| 11 |
Correct |
0 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
208 KB |
Output is correct |
| 13 |
Correct |
0 ms |
336 KB |
Output is correct |
| 14 |
Correct |
0 ms |
336 KB |
Output is correct |
| 15 |
Correct |
0 ms |
208 KB |
Output is correct |
| 16 |
Correct |
0 ms |
336 KB |
Output is correct |
| 17 |
Correct |
0 ms |
336 KB |
Output is correct |
| 18 |
Correct |
0 ms |
336 KB |
Output is correct |
| 19 |
Correct |
0 ms |
336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
0 ms |
208 KB |
Output is correct |
| 10 |
Correct |
0 ms |
208 KB |
Output is correct |
| 11 |
Correct |
0 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
208 KB |
Output is correct |
| 13 |
Correct |
0 ms |
336 KB |
Output is correct |
| 14 |
Correct |
0 ms |
336 KB |
Output is correct |
| 15 |
Correct |
0 ms |
208 KB |
Output is correct |
| 16 |
Correct |
0 ms |
336 KB |
Output is correct |
| 17 |
Correct |
0 ms |
336 KB |
Output is correct |
| 18 |
Correct |
0 ms |
336 KB |
Output is correct |
| 19 |
Correct |
0 ms |
336 KB |
Output is correct |
| 20 |
Correct |
1 ms |
336 KB |
Output is correct |
| 21 |
Correct |
0 ms |
336 KB |
Output is correct |
| 22 |
Correct |
1 ms |
336 KB |
Output is correct |
| 23 |
Correct |
1 ms |
336 KB |
Output is correct |
| 24 |
Correct |
6 ms |
540 KB |
Output is correct |
| 25 |
Correct |
3 ms |
464 KB |
Output is correct |
| 26 |
Correct |
3 ms |
464 KB |
Output is correct |
| 27 |
Correct |
3 ms |
428 KB |
Output is correct |
| 28 |
Correct |
2 ms |
336 KB |
Output is correct |
| 29 |
Correct |
3 ms |
416 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
0 ms |
208 KB |
Output is correct |
| 10 |
Correct |
0 ms |
208 KB |
Output is correct |
| 11 |
Correct |
0 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
208 KB |
Output is correct |
| 13 |
Correct |
0 ms |
336 KB |
Output is correct |
| 14 |
Correct |
0 ms |
336 KB |
Output is correct |
| 15 |
Correct |
0 ms |
208 KB |
Output is correct |
| 16 |
Correct |
0 ms |
336 KB |
Output is correct |
| 17 |
Correct |
0 ms |
336 KB |
Output is correct |
| 18 |
Correct |
0 ms |
336 KB |
Output is correct |
| 19 |
Correct |
0 ms |
336 KB |
Output is correct |
| 20 |
Correct |
1 ms |
336 KB |
Output is correct |
| 21 |
Correct |
0 ms |
336 KB |
Output is correct |
| 22 |
Correct |
1 ms |
336 KB |
Output is correct |
| 23 |
Correct |
1 ms |
336 KB |
Output is correct |
| 24 |
Correct |
6 ms |
540 KB |
Output is correct |
| 25 |
Correct |
3 ms |
464 KB |
Output is correct |
| 26 |
Correct |
3 ms |
464 KB |
Output is correct |
| 27 |
Correct |
3 ms |
428 KB |
Output is correct |
| 28 |
Correct |
2 ms |
336 KB |
Output is correct |
| 29 |
Correct |
3 ms |
416 KB |
Output is correct |
| 30 |
Correct |
15 ms |
3024 KB |
Output is correct |
| 31 |
Correct |
5 ms |
3024 KB |
Output is correct |
| 32 |
Correct |
16 ms |
3252 KB |
Output is correct |
| 33 |
Correct |
13 ms |
3132 KB |
Output is correct |
| 34 |
Correct |
935 ms |
4464 KB |
Output is correct |
| 35 |
Correct |
349 ms |
3664 KB |
Output is correct |
| 36 |
Correct |
30 ms |
3224 KB |
Output is correct |
| 37 |
Correct |
24 ms |
3136 KB |
Output is correct |
| 38 |
Correct |
19 ms |
3188 KB |
Output is correct |
| 39 |
Correct |
25 ms |
3240 KB |
Output is correct |
| 40 |
Correct |
795 ms |
4552 KB |
Output is correct |
| 41 |
Correct |
141 ms |
3664 KB |
Output is correct |
| 42 |
Correct |
95 ms |
3392 KB |
Output is correct |
| 43 |
Correct |
38 ms |
3876 KB |
Output is correct |
| 44 |
Correct |
764 ms |
3212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
0 ms |
208 KB |
Output is correct |
| 10 |
Correct |
0 ms |
208 KB |
Output is correct |
| 11 |
Correct |
0 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
208 KB |
Output is correct |
| 13 |
Correct |
0 ms |
336 KB |
Output is correct |
| 14 |
Correct |
0 ms |
336 KB |
Output is correct |
| 15 |
Correct |
0 ms |
208 KB |
Output is correct |
| 16 |
Correct |
0 ms |
336 KB |
Output is correct |
| 17 |
Correct |
0 ms |
336 KB |
Output is correct |
| 18 |
Correct |
0 ms |
336 KB |
Output is correct |
| 19 |
Correct |
0 ms |
336 KB |
Output is correct |
| 20 |
Correct |
1 ms |
336 KB |
Output is correct |
| 21 |
Correct |
0 ms |
336 KB |
Output is correct |
| 22 |
Correct |
1 ms |
336 KB |
Output is correct |
| 23 |
Correct |
1 ms |
336 KB |
Output is correct |
| 24 |
Correct |
6 ms |
540 KB |
Output is correct |
| 25 |
Correct |
3 ms |
464 KB |
Output is correct |
| 26 |
Correct |
3 ms |
464 KB |
Output is correct |
| 27 |
Correct |
3 ms |
428 KB |
Output is correct |
| 28 |
Correct |
2 ms |
336 KB |
Output is correct |
| 29 |
Correct |
3 ms |
416 KB |
Output is correct |
| 30 |
Correct |
15 ms |
3024 KB |
Output is correct |
| 31 |
Correct |
5 ms |
3024 KB |
Output is correct |
| 32 |
Correct |
16 ms |
3252 KB |
Output is correct |
| 33 |
Correct |
13 ms |
3132 KB |
Output is correct |
| 34 |
Correct |
935 ms |
4464 KB |
Output is correct |
| 35 |
Correct |
349 ms |
3664 KB |
Output is correct |
| 36 |
Correct |
30 ms |
3224 KB |
Output is correct |
| 37 |
Correct |
24 ms |
3136 KB |
Output is correct |
| 38 |
Correct |
19 ms |
3188 KB |
Output is correct |
| 39 |
Correct |
25 ms |
3240 KB |
Output is correct |
| 40 |
Correct |
795 ms |
4552 KB |
Output is correct |
| 41 |
Correct |
141 ms |
3664 KB |
Output is correct |
| 42 |
Correct |
95 ms |
3392 KB |
Output is correct |
| 43 |
Correct |
38 ms |
3876 KB |
Output is correct |
| 44 |
Correct |
764 ms |
3212 KB |
Output is correct |
| 45 |
Correct |
191 ms |
28588 KB |
Output is correct |
| 46 |
Correct |
26 ms |
28360 KB |
Output is correct |
| 47 |
Correct |
23 ms |
28340 KB |
Output is correct |
| 48 |
Correct |
257 ms |
34468 KB |
Output is correct |
| 49 |
Correct |
195 ms |
28444 KB |
Output is correct |
| 50 |
Execution timed out |
4054 ms |
34324 KB |
Time limit exceeded |
| 51 |
Halted |
0 ms |
0 KB |
- |
