# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
150707 | 맞WATLE (#200) | Bulb Game (FXCUP4_bulb) | C++17 | 2 ms | 380 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bulb.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3e5;
int N, LC[MAXN+10], ans;
int dp1[MAXN+10], dp2[MAXN+10];
vector<int> L, R, P;
void dfs1(int now)
{
if(L[now]<0) { LC[now]=(L[now]==-1); return; }
else
{
dfs1(L[now]);
P[L[now]]=now;
}
if(R[now]>=0)
{
dfs1(R[now]);
P[R[now]]=now;
}
LC[now]=LC[L[now]];
}
void dfs2(int now)
{
if(now==0)
{
if(L[now]>=0) dp1[now]=LC[L[now]];
else dp1[now]=(L[now]==-1);
}
else
{
if(L[now]>=0) dp1[now]=dp1[P[now]]&&LC[L[now]];
else dp1[now]=dp1[P[now]]&&(L[now]==-1);
}
if(L[now]>=0) dfs2(L[now]);
if(R[now]>=0) dfs2(R[now]);
if(L[now]<0)
{
dp2[now]=LC[now];
}
else
{
dp2[now]=LC[now]&&dp2[L[now]];
}
}
void dfs3(int now)
{
if(L[now]>=0) dfs3(L[now]);
//if(R[now]>=0) dfs3(R[now]);
if(R[now]>=0) ans|=dp1[now]&&dp2[R[now]];
else ans|=dp1[now];
}
int FindWinner(int _T, vector<int> _L, vector<int> _R)
{
int i, j;
L=_L; R=_R; N=L.size(); P.resize(N);
dfs1(0);
if(LC[0]==-2) return 0;
dfs2(0);
dfs3(0);
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |