oj.uz

Submission #62769

# Submission time Handle Problem Language Result Execution time Memory
62769 2018-07-30T03:14:32 Z zetapi Tropical Garden (IOI11_garden) C++14
49 / 100
 66 ms 38056 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[0]=dis;
		return ;
	}
	if(type==1)
		Distance[node][0]=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];
			if(Distance[A][0]>=0 and CycleLength[0]>0)
			{
				if(G[B]-Distance[A][0]>=0 and (G[B]-Distance[A][0])%CycleLength[0]==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 24016 KB Output is correct
2 Correct 25 ms 23904 KB Output is correct
3 Correct 24 ms 23860 KB Output is correct
4 Correct 24 ms 23840 KB Output is correct
5 Correct 27 ms 23892 KB Output is correct
6 Correct 26 ms 24000 KB Output is correct
7 Correct 30 ms 23900 KB Output is correct
8 Correct 30 ms 23908 KB Output is correct
9 Correct 27 ms 24028 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24016 KB Output is correct
2 Correct 25 ms 23904 KB Output is correct
3 Correct 24 ms 23860 KB Output is correct
4 Correct 24 ms 23840 KB Output is correct
5 Correct 27 ms 23892 KB Output is correct
6 Correct 26 ms 24000 KB Output is correct
7 Correct 30 ms 23900 KB Output is correct
8 Correct 30 ms 23908 KB Output is correct
9 Correct 27 ms 24028 KB Output is correct
10 Correct 25 ms 23908 KB Output is correct
11 Correct 34 ms 25552 KB Output is correct
12 Correct 47 ms 26868 KB Output is correct
13 Incorrect 66 ms 38056 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 24016 KB Output is correct
2 Correct 25 ms 23904 KB Output is correct
3 Correct 24 ms 23860 KB Output is correct
4 Correct 24 ms 23840 KB Output is correct
5 Correct 27 ms 23892 KB Output is correct
6 Correct 26 ms 24000 KB Output is correct
7 Correct 30 ms 23900 KB Output is correct
8 Correct 30 ms 23908 KB Output is correct
9 Correct 27 ms 24028 KB Output is correct
10 Correct 25 ms 23908 KB Output is correct
11 Correct 34 ms 25552 KB Output is correct
12 Correct 47 ms 26868 KB Output is correct
13 Incorrect 66 ms 38056 KB Output isn't correct
14 Halted 0 ms 0 KB -