#include "bulb.h"
#include<iostream>
using namespace std;
constexpr int LEFT = 0,RIGHT=1;
constexpr int RED = 100,BLUE=200;
int child[300010][2];
int col_memoi[300010];
int tobered_memoi[300010];
int color(int n){
if(n==-1) return RED;
else if(n==-2) return BLUE;
if(col_memoi[n]>0) return col_memoi[n];
return (col_memoi[n] = color(child[n][LEFT]));
}
int tobered(int n){
//cout << "tbr "<< n << endl;
if(n==-1) return RED;
else if(n==-2) return BLUE;
if(tobered_memoi[n]>0) return tobered_memoi[n];
if(color(child[n][RIGHT])==RED && tobered(child[n][LEFT]) == RED) tobered_memoi[n] = RED;
else tobered_memoi[n] = RIGHT;
return tobered_memoi[n];
}
int FindWinner(int T, std::vector<int> L, std::vector<int> R){
int N = L.size();
//root is always 0
for(int i=0;i<N;++i){
child[i][LEFT] = L[i];
child[i][RIGHT] = R[i];
if(L[i]<0){
if(L[i]==-1) col_memoi[i] = RED;
else if(L[i]==-2) col_memoi[i] = BLUE;
}
if(R[i]<0){
if(R[i]==-1) tobered_memoi[i] = RED;
else if(R[i]==-2) tobered_memoi[i] = BLUE;
}
}
if(color(0)==BLUE) return 0;//****
//go down, traverse the paths.
int node = 0;
while(node >= 0){
//are all alternate choices red now?
//if even one is blue, we are to try only until this one, then break. denoted by %%
//we try going right on this node
// is the node red to-be?
//cout << node << endl;
if(tobered(child[node][RIGHT])==RED && color(child[node][LEFT])==RED){
//yes, red wins.
return 1; //****
}
//%%
if(color(child[node][RIGHT])==BLUE){
return 0;//****
}
node = child[node][LEFT];
}
return 0;//****
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
296 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
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 |
- |
