Submission #172643

#	Time	Username	Problem	Language	Result	Execution time	Memory
172643		top34051	Bulb Game (FXCUP4_bulb)	C++17	0 / 100	3 ms	376 KiB

bulb

#include "bulb.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 5;

int n, T;
vector<int> L, R;
int res[maxn], lose[maxn], sumDown[maxn];

int odd, even, win;

void dfs(int u) {
	if(u >= n) return ;

	dfs(L[u]);
	dfs(R[u]);

	res[u] = res[L[u]];
	lose[u] = lose[L[u]] + (res[R[u]] == 0);
	sumDown[u] = sumDown[L[u]] + 1;

	printf("%d: %d %d %d\n",u,res[u],lose[u],sumDown[u]);
}

void solve(int u, int ok, int upLose, int sumUp) {
	if(u >= n) return ;

	solve(L[u], ok, upLose + (res[R[u]] == 0), sumUp + 1);
	solve(R[u], 0, upLose + (res[R[u]] == 0), sumUp + 1);
	
	if(ok) { // main line
		if(res[R[u]]) { // push to win
			odd = 1;
			if(upLose == 0 && lose[R[u]] == 0) { // opponent has to win
				win = 1;
			}
		}
		else { // push to lose
			even = 1;
			if(upLose == 0 && lose[R[u]] == 0 && sumUp + sumDown[R[u]] + 1 == n) {
				win = 1;
			}
		}
	}
}

int CNT = 0;

int FindWinner(int turns, vector<int> leftChild, vector<int> rightChild){
	T = turns; L = leftChild; R = rightChild; 
	n = (int)leftChild.size();

	CNT++;
	assert(CNT == 1);

	for(auto &t : L) if(t < 0) t = n - 1 - t;
	for(auto &t : R) if(t < 0) t = n - 1 - t;

	res[n] = 1;

	dfs(0);
	solve(0, 1, 0, 0);

	if(T % 2 != 0) {
		// if(res[0] == 1 && sumDown[0] != n) return 1;
		if(odd) return 1;
		return 0; 
	}

	if(res[0] == 0) return 0;

	if(sumDown[0] != n && even == 0) return 1;

	return win;
}

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