oj.uz

Submission #150593

# Submission time Handle Problem Language Result Execution time Memory
150593 2019-09-01T08:41:39 Z Seishun Buta Yarou wa Yumemiru Shoujo no Yume wo Minai(#3781, zscoder, tmwilliamlin168) Bulb Game (FXCUP4_bulb) C++17
100 / 100
 135 ms 28620 KB 
#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(L[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;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6900 KB Output is correct
2 Correct 7 ms 6936 KB Output is correct
3 Correct 8 ms 6928 KB Output is correct
4 Correct 8 ms 6876 KB Output is correct
5 Correct 8 ms 6904 KB Output is correct
6 Correct 7 ms 6876 KB Output is correct
7 Correct 7 ms 6876 KB Output is correct
8 Correct 7 ms 6880 KB Output is correct
9 Correct 7 ms 6876 KB Output is correct
10 Correct 7 ms 6904 KB Output is correct
11 Correct 7 ms 6904 KB Output is correct
12 Correct 7 ms 6896 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 7 ms 6864 KB Output is correct
3 Correct 8 ms 6900 KB Output is correct
4 Correct 7 ms 6936 KB Output is correct
5 Correct 8 ms 6928 KB Output is correct
6 Correct 8 ms 6876 KB Output is correct
7 Correct 8 ms 6904 KB Output is correct
8 Correct 7 ms 6876 KB Output is correct
9 Correct 7 ms 6876 KB Output is correct
10 Correct 7 ms 6880 KB Output is correct
11 Correct 7 ms 6876 KB Output is correct
12 Correct 7 ms 6904 KB Output is correct
13 Correct 7 ms 6904 KB Output is correct
14 Correct 7 ms 6896 KB Output is correct
15 Correct 7 ms 6904 KB Output is correct
16 Correct 7 ms 6904 KB Output is correct
17 Correct 8 ms 6924 KB Output is correct
18 Correct 8 ms 6904 KB Output is correct
19 Correct 7 ms 6904 KB Output is correct
20 Correct 8 ms 6904 KB Output is correct
21 Correct 8 ms 6904 KB Output is correct
22 Correct 8 ms 6904 KB Output is correct
23 Correct 8 ms 6904 KB Output is correct
24 Correct 8 ms 6912 KB Output is correct
25 Correct 8 ms 6892 KB Output is correct
26 Correct 8 ms 6920 KB Output is correct

Subtask #3
64.0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 7 ms 6864 KB Output is correct
3 Correct 8 ms 6900 KB Output is correct
4 Correct 7 ms 6936 KB Output is correct
5 Correct 8 ms 6928 KB Output is correct
6 Correct 8 ms 6876 KB Output is correct
7 Correct 8 ms 6904 KB Output is correct
8 Correct 7 ms 6876 KB Output is correct
9 Correct 7 ms 6876 KB Output is correct
10 Correct 7 ms 6880 KB Output is correct
11 Correct 7 ms 6876 KB Output is correct
12 Correct 7 ms 6904 KB Output is correct
13 Correct 7 ms 6904 KB Output is correct
14 Correct 7 ms 6896 KB Output is correct
15 Correct 7 ms 6904 KB Output is correct
16 Correct 7 ms 6904 KB Output is correct
17 Correct 8 ms 6924 KB Output is correct
18 Correct 8 ms 6904 KB Output is correct
19 Correct 7 ms 6904 KB Output is correct
20 Correct 8 ms 6904 KB Output is correct
21 Correct 8 ms 6904 KB Output is correct
22 Correct 8 ms 6904 KB Output is correct
23 Correct 8 ms 6904 KB Output is correct
24 Correct 8 ms 6912 KB Output is correct
25 Correct 8 ms 6892 KB Output is correct
26 Correct 8 ms 6920 KB Output is correct
27 Correct 97 ms 15620 KB Output is correct
28 Correct 116 ms 17868 KB Output is correct
29 Correct 118 ms 18264 KB Output is correct
30 Correct 135 ms 28620 KB Output is correct
31 Correct 132 ms 28284 KB Output is correct
32 Correct 112 ms 17044 KB Output is correct
33 Correct 115 ms 18468 KB Output is correct
34 Correct 115 ms 18472 KB Output is correct
35 Correct 116 ms 17032 KB Output is correct
36 Correct 115 ms 17796 KB Output is correct
37 Correct 115 ms 17184 KB Output is correct
38 Correct 115 ms 18472 KB Output is correct
39 Correct 116 ms 18568 KB Output is correct
40 Correct 115 ms 16892 KB Output is correct
41 Correct 117 ms 16784 KB Output is correct
42 Correct 117 ms 18452 KB Output is correct
43 Correct 115 ms 18436 KB Output is correct
44 Correct 115 ms 17808 KB Output is correct
45 Correct 115 ms 17184 KB Output is correct
46 Correct 116 ms 18080 KB Output is correct
47 Correct 115 ms 19488 KB Output is correct
48 Correct 115 ms 19756 KB Output is correct
49 Correct 119 ms 21204 KB Output is correct
50 Correct 118 ms 18336 KB Output is correct