Submission #149780

#	Time	Username	Problem	Language	Result	Execution time	Memory
149780		Powered By Zigui (#200)	Bulb Game (FXCUP4_bulb)	C++17	0 / 100	2 ms	348 KiB

bulb

#include "bulb.h"
using namespace std;

#define RED -1
#define BLUE -2

const int MAXN = 2e5 + 10;

int D[MAXN][3];
int LL[MAXN], RR[MAXN];
void dfs(int here){
	if(LL[here] > 0) {
		dfs(LL[here]);
		D[here][0] = D[LL[here]][0];
		if(D[LL[here]][1] != -1) D[here][1] |= D[LL[here]][1];
		if(D[LL[here]][2] != -1) {
			if(D[here][2] != -1) D[here][2] |= D[LL[here]][2];
			else D[here][2] = D[LL[here]][2];
		}
	}
	else {
		D[here][0] = (LL[here] == RED);
		D[here][2] = -1;
	}

	if(RR[here] > 0) {
		dfs(RR[here]);
		D[here][0] = D[LL[here]][0];
		if(D[RR[here]][0] != -1) D[here][1] |= D[RR[here]][0];
		D[here][2] |= D[RR[here]][1];
	}
	else D[here][1] = (RR[here] == RED);
}

int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	int N = L.size();
	T %= 2;

	for(int i = 0 ; i < N ; i++) LL[i] = L[i], RR[i] = R[i];
	for(int i = 0 ; i < N ; i++) D[i][2] = -1;

	dfs(0);

	if(T == 0) return (D[0][0] == 1) && (D[0][2] != 0);
	else return (D[0][1] == 1);
}

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