oj.uz

Submission #150581

# Submission time Handle Problem Language Result Execution time Memory
150581 2019-09-01T08:40:21 Z From The Sky(#3630, WhipppedCream, top34051, zoomswk) Bulb Game (FXCUP4_bulb) C++17
0 / 100
 4 ms 2680 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Incorrect 4 ms 2680 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -