oj.uz

Submission #150736

# Submission time Handle Problem Language Result Execution time Memory
150736 2019-09-01T08:52:37 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 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];
	else flow[u] = flow[L[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();
	dfs(0);
	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);
	}
	if(def == -2) return 0;
	return 1;
}

Compilation message

bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:68:6: warning: unused variable 'N' [-Wunused-variable]
  int N = L.size();
      ^
bulb.cpp:73:7: warning: variable 'found' set but not used [-Wunused-but-set-variable]
  bool found = false;
       ^~~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 25.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

Subtask #3
0 / 64.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