#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 (ml[0] == -2) {
return 0;
}
puts("cnm");
for (int i=0;i<N;i++) {
if (rc[i] == 1 && ml[i] == -1 && i == ml2[i] && ok[i]) {
printf("find %d\n",i);
return 1;
}
}
for (int i=0;i>=0;i=L[i]) {
if (ok[i] && R[i] == -1) {
return 1;
}
}
bool chain = true;
for (int i=0;i<N;i++) {
if (L[i] >= 0 && R[i] >= 0) {
chain = false;
}
}
if (chain) {
int down = 0, step = 0;
while(L[down] >= 0 && R[down] >= 0) {
if (L[down] >= 0) {
down = L[down];
} else {
down = R[down];
step++;
}
}
printf("fuck %d\n",step);
if (step == 0) {
if (ok[down]) {
return 1;
}
} else if (step == 1) {
if (ok[down] && R[down] == -1) {
return 1;
}
}
}
//puts("?");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
352 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
