#include "bulb.h"
const int RED = -1;
const int BLUE = -2;
using vi = std::vector<int>;
const int NMAX = 300000;
bool c[NMAX*4+3];
void SetTrue(int nl,int nr,int l,int r,int node){
if(l<=nl&&nr<=r){
c[node]=true; return;
}
else if(nr<l||r<nl) return;
int mid = (nl+nr)/2;
SetTrue(nl,mid,l,r,node*2+1);
SetTrue(mid+1,nr,l,r,node*2+2);
}
int N;
void SetTrue(int l,int r){if(l<=r) SetTrue(0,N-1,l,r,0);}
bool ReadBool(int nl,int nr,int x,int node){
if(c[node]) return true;
if(nl==nr) return c[node];
int mid = (nl+nr)/2;
if(x<=mid) return ReadBool(nl,mid,x,node*2+1);
else return ReadBool(mid+1,nr,x,node*2+2);
}
bool ReadBool(int x){return ReadBool(0,N-1,x,0);}
bool hasTwo[NMAX];
int L[NMAX], R[NMAX];
int reorder[NMAX];
int tc;
void ReorderDfs(const vi& _L, const vi& _R, int root=0){
int reroot = reorder[root];
if(_L[root] >= 0){
reorder[_L[root]] = ++tc;
L[reroot] = tc;
ReorderDfs(_L, _R, _L[root]);
}
else{
L[reroot] = _L[root];
}
if(_R[root] >= 0){
reorder[_R[root]] = ++tc;
R[reroot] = tc;
ReorderDfs(_L, _R, _R[root]);
}
else{
R[reroot] = _R[root];
}
}
void FindTwo(int root, vi& rv){
if(L[root]>=0) FindTwo(L[root], rv);
else if(rv.size()==2 && L[root]==BLUE){
hasTwo[rv[0]] = hasTwo[rv[1]] = true;
}
if(rv.size() < 2){
rv.push_back(root);
if(R[root]>=0) FindTwo(R[root], rv);
else if(rv.size()==2 && R[root] == BLUE){
hasTwo[rv[0]] = hasTwo[rv[1]] = true;
}
rv.pop_back();
}
}
void FindOne(){
int st = 0;
int it = 0;
while(1){
if(R[it]==BLUE){
SetTrue(it+1,N-1);
}
else if(R[it]>=0){
int st2 = R[it];
int it2 = st2;
while(L[it2]>=0) it2 = L[it2];
if(L[it2]==BLUE){
SetTrue(it+1, st2-1);
SetTrue(it2+1, N-1);
}
}
if(L[it]>=0) it = L[it];
else return;
}
}
int FindWinner(int T, std::vector<int> _L, std::vector<int> _R){
N = _L.size();
int it=0;
while(_L[it]>=0) it = _L[it];
if(_L[it]==BLUE) return 0;
ReorderDfs(_L, _R);
FindOne();
vi rv;
FindTwo(0, rv);
for(int i=0;i<N;i++){
if(hasTwo[i]) continue;
if(ReadBool(i)) continue;
return 1;
}
return 0;
}
