#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();
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);
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
