#include "bulb.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
int dp[555555]; //what color you get if you keep go left
int dp2[555555]; //what color you get if we go right from you and then spam left
int dp3[555555];
int sub[555555];
int a[555555];
int b[555555];
int crt[555555];
int dfs(int u)
{
if(dp[u]!=-1) return dp[u];
if(a[u]<0)
{
if(a[u]==-1) return (dp[u]=1);
else return (dp[u]=0);
}
return (dp[u]=dfs(a[u]));
}
int calcsiz(int u)
{
if(u<0) return 0;
if(sub[u]>=0) return sub[u];
return (sub[u]=calcsiz(a[u])+calcsiz(b[u])+1);
}
int dfs3(int u)
{
if(u<0) return 1;
if(dp3[u]>=0) return dp3[u];
if(dp2[u]==0) return (dp3[u]=0);
return (dp3[u]=dfs3(a[u]));
}
void calcrt(int u)
{
if(u<0) return ;
if(a[u]>=0) crt[a[u]]=crt[u];
if(b[u]>=0) crt[b[u]]=crt[u]+1;
calcrt(a[u]); calcrt(b[u]);
}
int F[1111];
int FindWinner2(int T, std::vector<int> L, std::vector<int> R)
{
int n = L.size();
for(int i=0;i<n;i++)
{
a[i]=L[i]; b[i]=R[i];
}
for(int i=0;i<n;i++)
{
int ex=0;
F[i]=1;
for(int j=0;j<n;j++)
{
F[j]^=1;
int cr=0;
while(cr>=0)
{
if(!F[cr]) cr=a[cr];
else cr=b[cr];
}
if(cr==-2) ex=1;
F[j]^=1;
}
F[i]=0;
if(!ex) return 1;
}
return 0;
}
int FindWinner(int T, std::vector<int> L, std::vector<int> R)
{
int n = L.size();
if(n==1)
{
if(a[0]==-1) return 1;
else return 0;
}
for(int i=0;i<n;i++)
{
a[i]=L[i]; b[i]=R[i];
}
//T is useless
memset(sub,-1,sizeof(sub));
memset(dp,-1,sizeof(dp));
memset(dp3,-1,sizeof(dp3));
for(int i=0;i<n;i++)
{
dp[i] = dfs(i);
sub[i] = calcsiz(i);
}
if(!dp[0]) return 0;
//dp[0] = 1
for(int i=0;i<n;i++)
{
if(b[i]<0)
{
if(b[i]==-1) dp2[i]=1;
else dp2[i]=0;
}
else
{
dp2[i]=dp[b[i]];
}
}
for(int i=0;i<n;i++)
{
dp3[i]=dfs3(i);
}
calcrt(0);
int cur=0;
int cnt=0;
bool ex=0;
for(int i=0;i<n;i++)
{
if(crt[i]>=2)
{
ex=1; break;
}
}
if(ex)
{
int cr=0; bool pos=1;
while(cr>=0)
{
if(!dp2[cr])
{
pos=0; break;
}
cr=a[cr];
}
if(pos) return 1;
}
//solo case
{
int cr=0; int bad=-1;
vi L;
while(cr>=0)
{
L.pb(cr);
if(!dp2[cr])
{
if(bad==-1) bad=cr;
else bad=-2;
}
cr=a[cr];
}
if(bad>=0)
{
cr=b[bad];
while(cr>=0)
{
if(dp2[cr])
{
return 1;
}
cr=a[cr];
}
}
else if(bad==-1)
{
for(int v:L)
{
int cr=b[v];
while(cr>=0)
{
if(dp2[cr])
{
return 1;
}
cr=a[cr];
}
}
}
}
while(cur>=0)
{
//flip cur
int bad=0;
if(b[cur]<0)
{
if(b[cur]==-2) bad=1;
}
else
{
if(dp[b[cur]]==0)
{
if(cnt+1+sub[b[cur]]<n)
{
bad=1;
}
}
}
if(bad) break;
//cerr<<cur<<' '<<b[cur]<<' '<<dp3[b[cur]]<<'\n';
if(dfs3(b[cur]))
{
return 1;
}
if(!dp2[cur]) break;
cur=a[cur]; cnt++;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
6904 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6904 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6876 KB |
Output is correct |
| 4 |
Correct |
7 ms |
6904 KB |
Output is correct |
| 5 |
Correct |
8 ms |
6936 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6904 KB |
Output is correct |
| 7 |
Correct |
8 ms |
6852 KB |
Output is correct |
| 8 |
Correct |
8 ms |
6840 KB |
Output is correct |
| 9 |
Correct |
7 ms |
6904 KB |
Output is correct |
| 10 |
Correct |
8 ms |
6876 KB |
Output is correct |
| 11 |
Correct |
8 ms |
6876 KB |
Output is correct |
| 12 |
Correct |
8 ms |
6924 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
