Submission #150581

#	Time	Username	Problem	Language	Result	Execution time	Memory
150581		From The Sky (#200)	Bulb Game (FXCUP4_bulb)	C++17	0 / 100	4 ms	2680 KiB

bulb

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef long long ll;

#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

const int md = 1e9+7;
const ll inf = 1e18;
const int maxn = 3e5+5;

template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }

#include "bulb.h"

vector<int> L, R;

int flow[maxn];
int flip[maxn];

int dp[maxn][2];

void dfs(int u)
{
	if(u< 0) return;
	dfs(L[u]); dfs(R[u]);
	if(L[u]< 0) flow[u] = L[u], flip[u] = R[u];
	else flow[u] = flow[L[u]], flip[u] = flow[R[u]];
}

int solve(int u, int st)
{
	if(u< 0)
	{
		if(u == -2) return 1;
		return 0;
	}
	if(dp[u][st] != -1) return dp[u][st];
	if(st == 0) return dp[u][st] = solve(L[u], 0);
	return dp[u][st] = solve(L[u], 1) or solve(R[u], 0);
}

vector<int> path;

void findpath(int u)
{
	if(u< 0) return;
	path.pb(u);
	findpath(L[u]);
}

int FindWinner(int T, std::vector<int> l, std::vector<int> r)
{
	L = l; R = r;
	int N = L.size();
	int def = flow[0];
	findpath(0);
	memset(dp, -1, sizeof dp);
	bool found = false;
	bool canB = false;
	for(int x : path)
	{
		bool tmp = canB || solve(R[x], 1);
		if(!tmp) found = true;
		canB = canB || solve(R[x], 0);
	}
	bool found2 = false;
	if(def == -1 && sz(path)< N) found2 = true;
	else
	{
		for(int x : path)
		{
			if(flow[R[x]] == -1) found2 = true;
		}
	}
	if(T%2)
	{
		return found2;
	}
	if(def == -2) return 0;
	return found;
}

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