| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 584542 |
2022-06-27T14:20:41 Z |
rainboy |
Game (APIO22_game) |
C++17 |
|
1 ms |
336 KB |
#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 = eo[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)
| ~~~~~~~~~~~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 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 |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
0 ms |
208 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
208 KB |
Wrong Answer[1] |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 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 |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
0 ms |
208 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
208 KB |
Wrong Answer[1] |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 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 |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
0 ms |
208 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
208 KB |
Wrong Answer[1] |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
1 ms |
208 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 |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
0 ms |
208 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
208 KB |
Wrong Answer[1] |
| 15 |
Halted |
0 ms |
0 KB |
- |
