제출 #150447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150447		=SUM(D1:D9) (#200)	Bulb Game (FXCUP4_bulb)	C++17	36 / 100	89 ms	14460 KiB

bulb

#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];
	col_memoi[n] = color(child[n][LEFT]);
	return col_memoi[n];
}
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] = BLUE;
	return tobered_memoi[n];
}
int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	int N = L.size();
	if(N==1 ) return L[0]==-1;
	//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)==RED && tobered(0)==RED) return 1;
	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;//****
}

• Subtask 1: 11 / 11
• Subtask 2: 25 / 25
• Subtask 3: 0 / 64