oj.uz

Submission #62773

# Submission time Handle Problem Language Result Execution time Memory
62773 2018-07-30T03:20:49 Z zetapi Tropical Garden (IOI11_garden) C++14
49 / 100
 66 ms 37224 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 CycleLength[4],Distance[MAX][4];
int lol,P_,Min[MAX],deg[MAX],res[MAX];

void dfs(int node,int type,int dis)
{
	if(node==P_ )
	{
      	CycleLength[type]=dis;
		return ;
	}
	if(type==1)
		Distance[node][lol]=dis;
	if(type==2)
	{
		for(auto A:vec[node])
		{
			if(Min[node]==A.first)
				dfs(A.first,A.second,dis+1);
		}
		return ;
	}
	for(auto A:vec[node])
	{
		if(Min[node]==A.first and deg[node]==2)
			continue;
		dfs(A.first,A.second,dis+1);
	}
	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;
		Distance[A][0]=-1;
		Distance[A][1]=-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)
			Min[u]=v;
		if(Min[v]==-1)
			Min[v]=u;
	}
	Distance[P][0]=0;
	Distance[P][1]=0;
	for(auto A:vec[P])
	{
		lol=(Min[P]==A.first);
		dfs(A.first,A.second,1);
	}
	int ok;
	for(int B=0;B<Q;B++)
	{
		for(int A=0;A<N;A++)
		{
			ok=0;
			ok|=Distance[A][0]==G[B];
			ok|=Distance[A][1]==G[B];
			if(Distance[A][0]>=0)
			{ 
				if(CycleLength[1]>0)
				{
					if(G[B]-Distance[A][0]>=0 and (G[B]-Distance[A][0])%CycleLength[1]==0)
						ok|=1;
                }
                if(CycleLength[2]>0)
                {
  	            	if(G[B]-Distance[A][0]>=0 and (G[B]-Distance[A][0])%CycleLength[2]==0)
						ok|=1;
				}
			}
			if(Distance[A][1]>=0)
			{
				if(CycleLength[2]>0)
				{
					if(G[B]-Distance[A][1]>=0 and (G[B]-Distance[A][1])%CycleLength[2]==0)
						ok|=1;
				}
				if(CycleLength[1]>0)
				{
					if(G[B]-Distance[A][1]>=0 and (G[B]-Distance[A][1])%CycleLength[1]==0)
						ok|=1;	
				}
			}
			res[B]+=ok;		
		}
	}
	for(int A=0;A<Q;A++)
		answer(res[A]);
	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;
}*/

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24008 KB Output is correct
2 Correct 24 ms 23920 KB Output is correct
3 Correct 26 ms 23972 KB Output is correct
4 Correct 25 ms 23800 KB Output is correct
5 Correct 23 ms 23812 KB Output is correct
6 Correct 24 ms 24032 KB Output is correct
7 Correct 24 ms 23808 KB Output is correct
8 Correct 26 ms 23912 KB Output is correct
9 Correct 27 ms 23928 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24008 KB Output is correct
2 Correct 24 ms 23920 KB Output is correct
3 Correct 26 ms 23972 KB Output is correct
4 Correct 25 ms 23800 KB Output is correct
5 Correct 23 ms 23812 KB Output is correct
6 Correct 24 ms 24032 KB Output is correct
7 Correct 24 ms 23808 KB Output is correct
8 Correct 26 ms 23912 KB Output is correct
9 Correct 27 ms 23928 KB Output is correct
10 Correct 25 ms 23904 KB Output is correct
11 Correct 34 ms 25300 KB Output is correct
12 Correct 46 ms 26276 KB Output is correct
13 Incorrect 66 ms 37224 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24008 KB Output is correct
2 Correct 24 ms 23920 KB Output is correct
3 Correct 26 ms 23972 KB Output is correct
4 Correct 25 ms 23800 KB Output is correct
5 Correct 23 ms 23812 KB Output is correct
6 Correct 24 ms 24032 KB Output is correct
7 Correct 24 ms 23808 KB Output is correct
8 Correct 26 ms 23912 KB Output is correct
9 Correct 27 ms 23928 KB Output is correct
10 Correct 25 ms 23904 KB Output is correct
11 Correct 34 ms 25300 KB Output is correct
12 Correct 46 ms 26276 KB Output is correct
13 Incorrect 66 ms 37224 KB Output isn't correct
14 Halted 0 ms 0 KB -