Submission #149396

#	Time	Username	Problem	Language	Result	Execution time	Memory
149396		강력한 한방 필살기 (#200)	Bulb Game (FXCUP4_bulb)	C++17	100 / 100	98 ms	16580 KiB

bulb

#include "bulb.h"

#include<stdio.h>
using namespace std;
const int N=301010;

int lblue[N],rlblue[N],lrlblue[N];
vector<int> L, R;
void dfs(int u){
	if(L[u]>=0){
		dfs(L[u]);
		lblue[u]=lblue[L[u]];
	}
	else if(L[u]==-2)lblue[u]=1;
	if(R[u]>=0){
		dfs(R[u]);
		rlblue[u]=lblue[R[u]];
	}
	else if(R[u]==-2)rlblue[u]=1;
	lrlblue[u]=rlblue[u];
	if(L[u]>=0)lrlblue[u]|=lrlblue[L[u]];
}

int chk[N];

int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	::L=L,::R=R;
	int n = L.size();
	int cur = 0;
	while(cur>=0)cur=L[cur];
	if(cur==-2)return 0;
	cur=0;
	int curlr=0;
	dfs(0);
	while(cur>=0){
		bool bad=false;
		if(R[cur]>=0&&lrlblue[R[cur]])bad=true;
		if(curlr)bad=true;
		if(!bad)return 1;
		curlr|=rlblue[cur];
		cur=L[cur];
	}
	cur=0,curlr=0;
	while(cur>=0){
		chk[cur]=1;
		if(R[cur]>=0){
			int cur2=R[cur];
			while(cur2>=0){
				chk[cur2]=1;
				bool bad=false;
				if(rlblue[cur2])bad=true;
				if(curlr)bad=true;
				if(L[cur]>=0&&lrlblue[L[cur]])bad=true;
				if(!bad)return 1;
				cur2=L[cur2];
			}
		}
		curlr|=rlblue[cur];
		cur=L[cur];
	}
	int cnt=0;
	for(int i=0;i<n;i++)if(chk[i])cnt++;
	if(cnt!=n){
		if(!lrlblue[0])return 1;
	}
	
	return 0;
}

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