#include "bulb.h"
#include <bits/stdc++.h>
int ml[300010],ml2[300010];
int rc[300010],fa[300010];
bool ok[300010];
void dfs(int x, std::vector<int> &L, std::vector<int> &R) {
if (L[x] > 0) {
dfs(L[x], L, R);
fa[L[x]] = x;
rc[L[x]] = rc[x];
ml[x] = ml[L[x]];
ml2[x] = ml2[L[x]];
} else {
ml[x] = L[x];
ml2[x] = x;
}
if (R[x] > 0) {
dfs(R[x], L, R);
fa[R[x]] = x;
rc[R[x]] = rc[x] + 1;
}
}
void dfs2(int x, std::vector<int> &L, std::vector<int> &R) {
if (x < 0) {
return;
}
if (x > 0) {
ok[x] = ok[fa[x]];
if (x == L[fa[x]]) {
ok[x] &= (ml[R[fa[x]]] == -1);
} else {
ok[x] &= (ml[L[fa[x]]] == -1);
}
}
dfs2(L[x],L,R);
dfs2(R[x],L,R);
}
int FindWinner(int T, std::vector<int> L, std::vector<int> R){
int N = L.size();
rc[0] = 0;
dfs(0,L,R);
ok[0] = true;
dfs2(0,L,R);
/*
for (int i=0;i<N;i++) {
printf("%d %d %d %d %d\n",i,ml[i],ml2[i],rc[i],ok[i]);
}
*/
if (T % 2 == 1) {
for (int i=0;i>=0;i=L[i]) {
if (R[i] == -1 || (ml[R[i]] == -1)) {
return 1;
}
}
if (ml[0] == -1) {
for (int i=0;i<N;i++) {
if (ml2[i] != ml2[0]) {
return 1;
}
}
}
return 0;
} else {
for (int i=0;i<N;i++) {
if (rc[i] == 1 && ml[i] == -1 && i == ml2[i] && ok[i]) {
return 1;
}
}
return 0;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
