Submission #150278

#	Time	Username	Problem	Language	Result	Execution time	Memory
150278		etyu (#200)	Bulb Game (FXCUP4_bulb)	C++17	100 / 100	100 ms	19492 KiB

bulb

#include "bulb.h"
#include <vector>
#include <iostream>
using namespace std;

int pl[300009], st[300009];
bool d[300009];
std::vector<int> l, r;

void dp(int n)
{
	if (pl[n] != 0) return;
	st[n] = 1;
	if (l[n] < 0) pl[n] = l[n];
	else {
		dp(l[n]);
		pl[n] = pl[l[n]];
		st[n] += st[l[n]];
	}
	if (r[n] >= 0) {
		dp(r[n]);
		st[n] += st[r[n]];
	}
	if ((l[n] >= 0 && d[l[n]]) || (r[n] == -2 || (r[n] >= 0 && pl[r[n]] == -2))) d[n] = true;
	else d[n] = false;
}

int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	int N = L.size();
	l = L; r = R;
	int rt = 0;
	for (int i = 0; i < N; i++) 
		if (pl[i] == 0) {
			dp(i);
			rt = i;
		}
	int hn = rt;
	while (hn >= 0)
		hn = l[hn];
	if (hn == -2) return 0;
	hn = rt;
	int sp = 0;
	while (hn >= 0) {
		int ts = sp;
		if (l[hn] >= 0) ts += st[l[hn]];
		bool f = true;
		if (ts != 0 && (r[hn] == -2 || (r[hn] >= 0 && pl[r[hn]] == -2))) f = false;
		if (r[hn] >= 0 && d[r[hn]]) f = false;
		if (f) return 1;
		if (r[hn] == -2 || (r[hn] >= 0 && pl[r[hn]] == -2)) return 0;
		if (r[hn] >= 0) sp += st[r[hn]];
		hn = l[hn];
	}
	return (sp != 0);
}

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