Submission #150946

#	Time	Username	Problem	Language	Result	Execution time	Memory
150946		dennisstar	Bulb Game (FXCUP4_bulb)	C++17	0 / 100	2 ms	376 KiB

bulb

#include "bulb.h"
using namespace std;
vector<int> L, R;
int win[300010], chk[300010];
int ww[300010], cc[300010];
int N;
void f(int lev)
{
	chk[lev]=1;
	if (L[lev]>=0) {
		if (chk[L[lev]]) win[lev]=win[L[lev]];
		else {
			f(L[lev]);
			win[lev]=win[L[lev]];
		}
	}
	else win[lev]=L[lev];
	if (R[lev]>=0&&!chk[R[lev]]) f(R[lev]);
}
int ff(int lev)
{
	if (cc[lev]) return ww[lev];
	cc[lev]=1;
	if (R[lev]>=0) ff(R[lev]);
	if (L[lev]==-1&&!(R[lev]==-1||win[R[lev]]==-1)) return 0;
	else if (L[lev]<0) return ww[lev]=1;
	else {
		if (!cc[L[lev]]) ff(L[lev]);
		if (ww[L[lev]]) return ww[lev]=1;
	}
	return 0;
}
int FindWinner(int T, vector<int> l, vector<int> r){
	N = L.size();
	for (int i:l) L.push_back(i);
	for (int i:r) R.push_back(i);
	f(0);
	if (win[0]==-2) return 0;
	ff(0);
	for (int i=0; i>=0; i=L[i]) {
		if (R[i]<0||(R[i]>=0&&ww[R[i]])) return 1;	
		if (R[i]==-2||win[R[i]]==-2) return 0;
	}
	return 0;
}

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