Submission #151102

#	Time	Username	Problem	Language	Result	Execution time	Memory
151102		pichulia	Bulb Game (FXCUP4_bulb)	C++17	100 / 100	299 ms	21640 KiB

bulb

#include "bulb.h"
#include<algorithm>
using namespace std;
int n;
int parent[600009];
int value[600009];
int m;
int root;
int res;
vector<int> a;
vector<int> b;
vector<int> w;
void dfs(int si, int sum)
{
	if (si >= n) {
		if (value[si] == -1)
		{
			value[si] = sum;
		}
		return;
	}
	dfs(a[si], sum);
	dfs(b[si], sum + 1);
	value[si] = min(value[a[si]], value[b[si]]);
}
void dfs2(int si)
{
	if (si >= n) {
		return;
	}
	dfs2(a[si]);
	dfs2(b[si]);
	value[si] = min(value[a[si]], value[b[si]]);
}
void add_naive(int si, int val) {
	if (si >= n) {
		value[si] += val;
		return;
	}
	add_naive(a[si], val);
	add_naive(b[si], val);
	value[si] = min(value[a[si]], value[b[si]]);
}
void flip_naive(int si, int type) {
	if (type == 0) {
		add_naive(a[si], 1);
		add_naive(b[si], -1);
	}
	else {
		add_naive(a[si], -1);
		add_naive(b[si], 1);
	}
}
void dfs_type2(int si)
{
	if (si >= n)return;
	if (value[b[si]] > 2) { res = 1; return; }
	dfs_type2(b[si]);
	if (res == 1)return;
	dfs_type2(a[si]);
}
void precal(int si) {
	if (si >= n)return;
	if (value[a[si]] == 1) {
		w.push_back(si);
		return;
	}
	if(value[b[si]] == 1)
		precal(b[si]);
}
void deepdark(int si, int wi)
{
	if (si >= n)return;
	if (si != wi)
	{
		if (b[si] < n) {
			res = 0;
			return;
		}
		deepdark(a[si], wi);
	}
	else {
		if (a[si] < n)
		{
			res = 0;
			return;
		}
		deepdark(b[si], wi);
	}
}
int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	n = L.size();
	a = L;
	b = R;
	m = n;
	int i, j, k;
	for (i = 0; i < n; i++) {
		parent[i] = i;
	}
	for (i = 0; i < n; i++) {
		if (L[i] >= 0)
		{
			parent[L[i]] = i;
		}
		else {
			if (L[i] == -1)
				value[m] = 999999;
			else
				value[m] = -1;
			a[i] = m;
			parent[m] = i;
			m++;
		}
		if (R[i] >= 0)
		{
			parent[R[i]] = i;
		}
		else {
			if (R[i] == -1)
				value[m] = 999999;
			else
				value[m] = -1;
			b[i] = m;
			parent[m] = i;
			m++;
		}
	}
	for (i = 0; i < n; i++) { if (parent[i] == i)break; }
	root = i;
	res = 0;
	dfs(root, 0);
	if (value[root] == 0) return 0;
	if (n <= 100) {
		for (i = 0; i < n; i++) {
			flip_naive(i, 0);
			for (j = 0; j < n; j++) {
				if (i == j) { flip_naive(j, 1); }
				else { flip_naive(j, 0); }
				dfs2(root);
				bool nono = false;
				if (value[root] == 0) nono = true;

				if (i == j) { flip_naive(j, 0); }
				else { flip_naive(j, 1); }

				if (nono)break;
			}
			flip_naive(i, 1);
			if (j == n) {
				//printf("%d is answer\n", i);
				break;
			}
		}
		return (i < n);
	}
	if (value[root] > 2)return 1;
	else if (value[root] == 2) {
		dfs_type2(root);
	}
	else {
		int superroot = root;
		while (root < n)
		{
			w.clear();
			precal(root);
			if (w.size() > 0)
			{
				flip_naive(w[0], 0);
				dfs2(superroot);
				//	printf("%d --> %d\n", w[0], value[root]);
				if (value[superroot] == 1) res = 0;
				else if (value[superroot] >= 2) res = 1;
				else {
					res = 1;
					deepdark(superroot, w[0]);
				}
				if (res == 1)
					break;
				flip_naive(w[0], 1);
			}
			root = a[root];
		}
	}
	return res;
}

Compilation message (stderr)

bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:96:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^

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