oj.uz

답안 #62825

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
62825 2018-07-30T12:00:02 Z zetapi 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
49 / 100
 66 ms 37468 KB 
#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++)
		{
			ok=0;
			final=G[A];
			ok|=(Distance[B]==final);
          	final-=Distance[B];
          	if(dp[0].first!=-1)
          		ok|=cal(final,dp[0].second);
          	if(dp[1].first!=-1)
          		ok|=cal(final,dp[1].second);
			/*if(type[B]==0 or deg[P]==1)	//We'll exit for first time using Min
			{
				final-=Distance[B];
				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)// Min-Min-Min
				{
					ok|=cal(final,dp[0].second);
				}
			}
			else if(type[B]==1)	//We'll exit this time using SecMin
			{
				final-=Distance[B];
				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,1};
	int R[][2]={{1,0},{1,2},{3,2},{1,3},{4,2}};
	count_routes(5,5,2,R,2,G);
	return 0;
}*/

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:174:12: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
            if(dp[1].first!=-1)
            ^~
garden.cpp:214:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    res[A]+=ok;
    ^~~

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 24048 KB Output is correct
2 Correct 31 ms 23988 KB Output is correct
3 Correct 30 ms 23952 KB Output is correct
4 Correct 24 ms 23804 KB Output is correct
5 Correct 25 ms 23848 KB Output is correct
6 Correct 25 ms 24028 KB Output is correct
7 Correct 25 ms 23812 KB Output is correct
8 Correct 24 ms 23932 KB Output is correct
9 Correct 26 ms 24032 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 24048 KB Output is correct
2 Correct 31 ms 23988 KB Output is correct
3 Correct 30 ms 23952 KB Output is correct
4 Correct 24 ms 23804 KB Output is correct
5 Correct 25 ms 23848 KB Output is correct
6 Correct 25 ms 24028 KB Output is correct
7 Correct 25 ms 23812 KB Output is correct
8 Correct 24 ms 23932 KB Output is correct
9 Correct 26 ms 24032 KB Output is correct
10 Correct 25 ms 23900 KB Output is correct
11 Correct 33 ms 25336 KB Output is correct
12 Correct 46 ms 26496 KB Output is correct
13 Incorrect 66 ms 37468 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 24048 KB Output is correct
2 Correct 31 ms 23988 KB Output is correct
3 Correct 30 ms 23952 KB Output is correct
4 Correct 24 ms 23804 KB Output is correct
5 Correct 25 ms 23848 KB Output is correct
6 Correct 25 ms 24028 KB Output is correct
7 Correct 25 ms 23812 KB Output is correct
8 Correct 24 ms 23932 KB Output is correct
9 Correct 26 ms 24032 KB Output is correct
10 Correct 25 ms 23900 KB Output is correct
11 Correct 33 ms 25336 KB Output is correct
12 Correct 46 ms 26496 KB Output is correct
13 Incorrect 66 ms 37468 KB Output isn't correct
14 Halted 0 ms 0 KB -