Submission #62838

#	Time	Username	Problem	Language	Result	Execution time	Memory
62838		zetapi	Tropical Garden (IOI11_garden)	C++14	100 / 100	3026 ms	40952 KiB

garden

#include "garden.h"
#include "gardenlib.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define	ll  long long
#define itr ::iterator 
 
typedef pair<int,int>  pii;
 
const int MAX=1e6;
 
vector<pii> vec[MAX];
 
int P_,lol,deg[MAX],res[MAX];
int type[MAX],Distance[MAX];
int Min[MAX],SecMin[MAX],mark[MAX][2];
pii dp[2];

bool cal(int X,int Y)
{
	return (X>=0 and Y>0 and X%Y==0);
}


void dfs(int node,int types,int dis)
{
	if(node==P_)
		return ;
	else if(types==1)
	{
		type[node]=lol;
		Distance[node]=dis;
		for(auto A:vec[node])
		{
			if(deg[node]>1 and A.first==Min[node])
				continue;
			dfs(A.first,A.second,dis+1);
		}
		return ;
	}
	else if(types==2)
	{
		for(auto A:vec[node])
			if(A.first==Min[node])
				dfs(A.first,A.second,dis+1);
		return ;
	}
	return ;
}
 
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	P_=P;
	int u,v;
	for(int A=0;A<N;A++)
	{
		Min[A]=-1;
		SecMin[A]=-1;
		type[A]=-1;
		Distance[A]=-1;
	}
	for(int A=0;A<M;A++)
	{
		u=R[A][0];
		v=R[A][1];
		if(deg[u]<2)	
		{
			++deg[u];
			vec[v].pb(mp(u,deg[u]));
		}
		if(deg[v]<2)
		{
			++deg[v];
			vec[u].pb(mp(v,deg[v]));
		}
		if(Min[u]!=-1 and SecMin[u]==-1)
			SecMin[u]=v;
		if(Min[v]!=-1 and SecMin[v]==-1)
			SecMin[v]=u;
		if(Min[u]==-1)
			Min[u]=v;
		if(Min[v]==-1)
			Min[v]=u;
	}
	Distance[P]=0;
	type[P]=0;
	for(auto A:vec[P])
	{
		lol=(A.first==Min[P]);
		dfs(A.first,A.second,1);
	}

	dp[0]=mp(-1,0);
	dp[1]=mp(-1,0);
	int cur=P,pre=-1;
	while(true)
	{
		dp[0].second++;
		if(deg[cur]>1 and Min[cur]==pre)
		{
			if(mark[cur][0])
				break;
			mark[cur][0]=1;
			pre=cur;
			cur=SecMin[cur];
		}
		else
		{
			if(mark[cur][1])
				break;
			mark[cur][1]=1;
			pre=cur;
			cur=Min[cur];
		}
		if(cur==P)
		{
			dp[0].first=(pre==Min[P]);
			break;
		}
	}

	for(int A=0;A<N;A++)
	{
		mark[A][0]=0;
		mark[A][1]=0;
	}
	if(deg[P]>1)
	{
		pre=P;
		cur=SecMin[P];
		dp[1].second++;
		while(true)
		{
			dp[1].second++;
			if(deg[cur]>1 and Min[cur]==pre)
			{
				if(mark[cur][0])
					break;
				mark[cur][0]=1;
				pre=cur;
				cur=SecMin[cur];
			}
			else
			{
				if(mark[cur][1])
					break;
				mark[cur][1]=1;
				pre=cur;
				cur=Min[cur];
			}
			if(cur==P)
			{
				dp[1].first=(pre==Min[P]);
				break;
			}		
		}
	}	

	int ok,final;
	for(int A=0;A<Q;A++)
	{
		for(int B=0;B<N;B++)
		{
			if(Distance[B]==-1)
				continue;
			ok=0;
			final=G[A];
			ok|=(Distance[B]==final);
          	final-=Distance[B];
			if(type[B]==0 or deg[P]==1)	//We'll exit for first time using Min
			{
				if(dp[0].first==1 and dp[1].first==0)// Min-SecMin-Min-SecMin
				{
					ok|=cal(final,dp[0].second+dp[1].second);
					final-=dp[0].second;
					ok|=cal(final,dp[0].second+dp[1].second);
				}
				else if(dp[0].first==1 and dp[1].first==1)// Min-SecMin-SecMin-SecMin
				{	
					final-=dp[0].second;
					ok|=cal(final,dp[1].second);
				}
				else if(dp[0].first==0 or (dp[0].first==1 and deg[P]==1))// Min-Min-Min
				{
					ok|=cal(final,dp[0].second);
				}
			}
			else if(type[B]==1)	//We'll exit this time using SecMin
			{
				if(dp[1].first==0 and dp[0].first==1)// SecMin-Min-SecMin-Min
				{
					ok|=cal(final,dp[1].second+dp[0].second);
					final-=dp[1].second;
					ok|=cal(final,dp[1].second+dp[0].second);
				}
				else if(dp[1].first==0 and dp[0].first==0)// SecMin-Min-Min-Min
				{
					final-=dp[1].second;
					ok|=cal(final,dp[0].second);
				}
				else if(dp[1].first==1)//SecMin-SecMin-SecMin
				{
					ok|=cal(final,dp[1].second);
				}
			}
			res[A]+=ok;
		}
	}
	for(int A=0;A<Q;A++)
		answer(res[A]);
		//cout<<res[A]<<"\n";
	return ;
}
 
/*signed main()
{
	ios_base::sync_with_stdio(false);
 
	
	int G[]={3};
	int R[][2]={{1,2},{0,1},{0,3},{3,4},{4,5},{1,5}};
	count_routes(6,6,0,R,1,G);
	return 0;
}*/

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31