Submission #150162

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

bulb

#include <bits/stdc++.h>
#include "bulb.h"

using namespace std;

int N;
vector<int> l, r, whr, good, down;

void DFS(int nod)
{
	if(nod < 0)	return;
	DFS(l[nod]);
	DFS(r[nod]);

	if(l[nod] < 0)	whr[nod] = l[nod];
	else	whr[nod] = whr[ l[nod] ];

	good[nod] = (whr[nod] == -1);
	if(r[nod] < 0)	good[nod] &= (r[nod] == -1);
	else	good[nod] &= (whr[ r[nod] ] == -1);

	if(l[nod] < 0)	down[nod] = good[nod];
	else	down[nod] = good[nod] & down[ l[nod] ];
}

int DFS2(int nod)
{
	if(r[nod] > 0 && down[ r[nod] ])	return 1;

	if(l[nod] < 0)
	{
		if(good[nod])	return 1;
		return 0;
	}

	if(good[nod])	return DFS2(l[nod]);
	return 0;
}

int FindWinner(int T, std::vector<int> L, std::vector<int> R)
{
	N = L.size();
	l = L, r = R;
	whr.resize(N); good.resize(N); down.resize(N);
	DFS(0);
	if(whr[0] == -2)	return 0;
	int ans = DFS2(0);
	return ans;
}

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