#include "bulb.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
int n, T;
vector<int> L, R;
int res[maxn], lose[maxn], sumDown[maxn];
int bad, win;
void dfs(int u) {
if(u >= n) return ;
dfs(L[u]);
dfs(R[u]);
res[u] = res[L[u]];
lose[u] = lose[L[u]] + (res[R[u]] == 0);
sumDown[u] = sumDown[L[u]] + 1;
}
void solve(int u, int ok, int upLose, int sumUp) {
if(u >= n) return ;
solve(L[u], ok, upLose + (res[R[u]] == 0), sumUp + 1);
solve(R[u], 0, upLose + (res[R[u]] == 0), sumUp + 1);
if(ok) { // main line
if(res[R[u]]) { // push to win
if(upLose == 0 && lose[R[u]] == 0) { // opponent has to win
win = 1;
}
}
else { // push to lose
bad = 1;
if(upLose == 0 && lose[R[u]] == 0 && sumUp + sumDown[R[u]] == n - 1) {
win = 1;
}
}
}
}
int FindWinner(int turns, vector<int> leftChild, vector<int> rightChild){
T = turns; L = leftChild; R = rightChild;
n = (int)leftChild.size();
for(auto &t : L) if(t < 0) t = n - 1 - t;
for(auto &t : R) if(t < 0) t = n - 1 - t;
res[n] = 1;
dfs(0);
solve(0, 1, 0, 0);
if(res[0] == 0) return 0;
if(sumDown[0] != n && bad == 0) return 1;
return win;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
3 ms |
376 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
352 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
3 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
3 ms |
376 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
424 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
504 KB |
Output is correct |
| 19 |
Correct |
2 ms |
504 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
2 ms |
376 KB |
Output is correct |
| 23 |
Correct |
2 ms |
380 KB |
Output is correct |
| 24 |
Correct |
2 ms |
376 KB |
Output is correct |
| 25 |
Correct |
2 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
352 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
3 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
3 ms |
376 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
424 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
504 KB |
Output is correct |
| 19 |
Correct |
2 ms |
504 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
2 ms |
376 KB |
Output is correct |
| 23 |
Correct |
2 ms |
380 KB |
Output is correct |
| 24 |
Correct |
2 ms |
376 KB |
Output is correct |
| 25 |
Correct |
2 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
376 KB |
Output is correct |
| 27 |
Correct |
103 ms |
13816 KB |
Output is correct |
| 28 |
Correct |
103 ms |
13792 KB |
Output is correct |
| 29 |
Correct |
111 ms |
13816 KB |
Output is correct |
| 30 |
Correct |
123 ms |
32604 KB |
Output is correct |
| 31 |
Correct |
117 ms |
32504 KB |
Output is correct |
| 32 |
Correct |
102 ms |
13692 KB |
Output is correct |
| 33 |
Correct |
101 ms |
13688 KB |
Output is correct |
| 34 |
Correct |
102 ms |
13892 KB |
Output is correct |
| 35 |
Correct |
102 ms |
13788 KB |
Output is correct |
| 36 |
Correct |
101 ms |
13688 KB |
Output is correct |
| 37 |
Correct |
103 ms |
13692 KB |
Output is correct |
| 38 |
Correct |
118 ms |
13832 KB |
Output is correct |
| 39 |
Correct |
112 ms |
13688 KB |
Output is correct |
| 40 |
Correct |
102 ms |
13688 KB |
Output is correct |
| 41 |
Correct |
103 ms |
13948 KB |
Output is correct |
| 42 |
Correct |
101 ms |
13740 KB |
Output is correct |
| 43 |
Correct |
103 ms |
13816 KB |
Output is correct |
| 44 |
Correct |
102 ms |
13816 KB |
Output is correct |
| 45 |
Correct |
102 ms |
13876 KB |
Output is correct |
| 46 |
Correct |
102 ms |
13660 KB |
Output is correct |
| 47 |
Correct |
106 ms |
17864 KB |
Output is correct |
| 48 |
Correct |
105 ms |
17912 KB |
Output is correct |
| 49 |
Correct |
106 ms |
18040 KB |
Output is correct |
| 50 |
Correct |
105 ms |
18040 KB |
Output is correct |
