Submission #762435

#	Time	Username	Problem	Language	Result	Execution time	Memory
762435		goodbyehanbyeol	Bulb Game (FXCUP4_bulb)	C++17	100 / 100	107 ms	40648 KiB

bulb

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

int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	int n = L.size();
	vector<vector<int>> way(n, vector<int>(2));
	for(int i = 0; i < n; ++i){
		way[i][0] = L[i];
		way[i][1] = R[i];
	} 

	vector<int> tchk(n), ocnt(n);

	int mn = (int)1e9;
	vector<int> diff;
	auto dfs = [&](auto&&self, int x, int pre)->void{
		if(x == -2){
			mn = min(mn, (int)diff.size());
			if((int)diff.size() == 2){
				tchk[diff[0]] = tchk[diff[1]] = 1;
			}
			if((int)diff.size() == 1){
				ocnt[pre] += 1;
			}
			return;
		}
		if(x == -1) return;

		self(self, way[x][0], x);
		diff.push_back(x);
		self(self, way[x][1], x);
		diff.pop_back();
		if(way[x][0] >= 0) ocnt[x] += ocnt[way[x][0]];
		if(way[x][1] >= 0) ocnt[x] += ocnt[way[x][1]];
	};
	dfs(dfs, 0, -1);

	if(mn == 0) return 0;
	if(mn >= 3) return 1;
	if(mn == 2){
		for(int i = 0; i < n; ++i){
			if(!tchk[i]){
				return 1;
			}
		}
		return 0;
	}

	int can = 0;
	auto onesol = [&](auto&&self, int x)->void{
		if(way[x][0] < 0) return;
		if(ocnt[x] != ocnt[way[x][0]]) return;
		if(!tchk[x]){
			can = 1;
			return;
		}
		self(self, way[x][0]);
	};
	onesol(onesol, 0);

	int can2 = 1, tcnt = 0, ed = 0;
	for(int i = 0; i < n; ++i){
		if(way[i][0] >= 0 && way[i][1] >= 0) can2 = 0;
		tcnt += (way[i][0] == -2) + (way[i][1] == -2);
		if(way[i][0] < 0 && way[i][1] < 0){
			ed |= (way[i][0] == -2 || way[i][1] == -2);
		}
	}
	if(can || (can2 && tcnt == 1 && ed)) return 1;

	return 0;
}

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