#include "bulb.h"
// Standard libraries
#include <stdio.h>
#include <vector>
// Global attributes
int N; // size
std::vector<int> left_ancestor_destination;
std::vector<int> leftchild, rightchild; // red -1 blue -2
std::vector<bool> perfect_red; // is this group perfect red?
std::vector<bool> final_left_red; // is this group's destination red?
// Set ancestor destination, perfect_red and final_left_red.
// Assuming all switches are left.
void set_left_ancestor_destinations(int now){
if(leftchild[now] >= 0){
left_ancestor_destination[leftchild[now]] = left_ancestor_destination[now];
set_left_ancestor_destinations(leftchild[now]);
}
else{
final_left_red[left_ancestor_destination[now]] = (leftchild[now] == -1);
if(leftchild[now] == -2) perfect_red[left_ancestor_destination[now]] = false;
}
if(rightchild[now] >= 0){
left_ancestor_destination[rightchild[now]] = rightchild[now];
set_left_ancestor_destinations(rightchild[now]);
if(!final_left_red[rightchild[now]]) // If this route leads to blue
perfect_red[left_ancestor_destination[now]] = false;
}
else{
if(rightchild[now] == -2) perfect_red[left_ancestor_destination[now]] = false;
}
}
// Solver function
int FindWinner(int T, std::vector<int> L, std::vector<int> R){
N = L.size(); // size
// Switches
leftchild = L, rightchild = R;
perfect_red.resize(N, true);
// Set left ancestor destination
left_ancestor_destination.resize(N, -1);
perfect_red.resize(N, true);
final_left_red.resize(N, true);
left_ancestor_destination[0] = 0;
set_left_ancestor_destinations(0);
// Debug
/*printf("Set attributes using DFS.\n");
for(int i=0; i<N; i++){
printf("Node %d: left ancestor %d, leftchild %d, rightchild %d\n",
i, left_ancestor_destination[i], leftchild[i], rightchild[i]);
if(left_ancestor_destination[i] == i){
printf("\t[Boss] final left red %c, perfect red %c\n",
final_left_red[i] ? 'T':'F', perfect_red[i] ? 'T': 'F');
}
} fflush(stdout);*/
// Always impossible
if(!final_left_red[0]) return false;
// Search on changing
int now = 0;
bool right_are_reds_so_far = true;
while(now >= 0 && right_are_reds_so_far){
// 0 -> .. (leftslide) .. -> now --R-> rightchild -> .. (leftslide) -> leaf ?
if(rightchild[now] >= 0){
if(perfect_red[rightchild[now]]) return true;
}
// Right are reds so far?
if(rightchild[now] >= 0){
if(!final_left_red[rightchild[now]]) right_are_reds_so_far = false;
}
else if(rightchild[now] == -2) right_are_reds_so_far = false;
// Go next step
now = leftchild[now];
}
// Last chance: Can we do outside-movement?
if(perfect_red[0]){
}
// No way
return false;
}
