oj.uz

Submission #62665

# Submission time Handle Problem Language Result Execution time Memory
62665 2018-07-29T17:15:23 Z zetapi Tropical Garden (IOI11_garden) C++14
49 / 100
 69 ms 38084 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];

ll P_,CycleLength,Min[MAX],Distance[MAX],deg[MAX],res[MAX];

void dfs(int node,int type,int dis)
{
	//cout<<node<<" "<<type<<" "<<dis<<" min bhi dekh lo "<<Min[node]<<"\n";
	if(node==P_)
	{
		CycleLength=dis;
		return ;
	}
	if(type==1 and Distance[node]==-1)
		Distance[node]=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++)
		Distance[A]=-1,Min[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)
			Min[u]=v;
		if(Min[v]==-1)
			Min[v]=u;
	}
	Distance[P]=0;
	for(auto A:vec[P])
		dfs(A.first,A.second,1);
	for(int B=0;B<Q;B++)
	{
		for(int A=0;A<N;A++)
		{
			if(Distance[A]==-1)
				continue;
			else if(CycleLength==0)
				res[B]+=Distance[A]==G[B];
			else if(G[B]-Distance[A]>=0 and (G[B]-Distance[A])%CycleLength==0)
				res[B]++;
		}
	}
	for(int A=0;A<Q;A++)
		answer(res[A]);
	//cout<<res;
	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 24 ms 23928 KB Output is correct
2 Correct 25 ms 23900 KB Output is correct
3 Correct 24 ms 23860 KB Output is correct
4 Correct 25 ms 23800 KB Output is correct
5 Correct 25 ms 23772 KB Output is correct
6 Correct 28 ms 24028 KB Output is correct
7 Correct 25 ms 23896 KB Output is correct
8 Correct 27 ms 23876 KB Output is correct
9 Correct 23 ms 24056 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 25 ms 23900 KB Output is correct
3 Correct 24 ms 23860 KB Output is correct
4 Correct 25 ms 23800 KB Output is correct
5 Correct 25 ms 23772 KB Output is correct
6 Correct 28 ms 24028 KB Output is correct
7 Correct 25 ms 23896 KB Output is correct
8 Correct 27 ms 23876 KB Output is correct
9 Correct 23 ms 24056 KB Output is correct
10 Correct 28 ms 23784 KB Output is correct
11 Correct 40 ms 25464 KB Output is correct
12 Correct 50 ms 26816 KB Output is correct
13 Incorrect 69 ms 38084 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 25 ms 23900 KB Output is correct
3 Correct 24 ms 23860 KB Output is correct
4 Correct 25 ms 23800 KB Output is correct
5 Correct 25 ms 23772 KB Output is correct
6 Correct 28 ms 24028 KB Output is correct
7 Correct 25 ms 23896 KB Output is correct
8 Correct 27 ms 23876 KB Output is correct
9 Correct 23 ms 24056 KB Output is correct
10 Correct 28 ms 23784 KB Output is correct
11 Correct 40 ms 25464 KB Output is correct
12 Correct 50 ms 26816 KB Output is correct
13 Incorrect 69 ms 38084 KB Output isn't correct
14 Halted 0 ms 0 KB -