oj.uz

Submission #13705

# Submission time Handle Problem Language Result Execution time Memory
13705 2015-03-16T04:03:19 Z progressive Tropical Garden (IOI11_garden) C++
0 / 100
 12 ms 11116 KB 
#include "garden.h"
#include "gardenlib.h"
#include<vector>
using namespace std;
#define MAXN 151000
vector<int> connexion[MAXN];
int destination[2*MAXN];
vector<int> revdest[2*MAXN];
int dist1[2*MAXN];
int dist2[2*MAXN];
bool vst[2*MAXN];
int incycle1=0;
int incycle2=0;
int PP,NN;
void dfs1(int i,int l)
{
	if(i==PP && vst[i]) incycle1=l;
	if(vst[i]) return ;
	vst[i]=true;
	dist1[i]=l;
	for(int x=0;x<revdest[i].size();x++)
		dfs1(revdest[i][x],l+1);
	return;
}
void dfs2(int i,int l)
{
	if(i==PP+NN && vst[i]) incycle2=l;
	if(vst[i]) return;
	vst[i]=true;
	dist2[i]=l;
	for(int x=0;x<revdest[i].size();x++)
		dfs2(revdest[i][x],l+1);
	return;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	NN=N;
	PP=P;
	for(int i=0;i<M;i++)
	{
		connexion[R[i][0]].push_back(R[i][1]);
		connexion[R[i][1]].push_back(R[i][0]);
	}
	for(int i=0;i<N;i++)
	{
		destination[i+N]=destination[i]=connexion[i][0];
		if(connexion[i].size()!=1)
			destination[i+N]=connexion[i][1];
	}
	for(int i=0;i<2*N;i++)
	{
		if(connexion[destination[i]][0]==i%N)
			revdest[destination[i]+N].push_back(i);
		else
			revdest[destination[i]].push_back(i);
	}
	dfs1(P,0);
	for(int i=0;i<2*N;i++) vst[i]=false;
	dfs2(P+N,0);
	/*
	for(int i=0;i<2*N;i++) printf("%d ",dist1[i]);
	printf("%d ",incycle1);
	puts("");
	for(int i=0;i<2*N;i++) printf("%d ",dist2[i]);
	printf("%d ",incycle2);
	*/
	for(int i=0;i<Q;i++)
	{
		int cnt=0;
		for(int j=0;j<N;j++)
		{
			if(G[i]>=dist1[j])
			{
				if(incycle1==0)
				{
					if(G[i]==dist1[j])
					{
						cnt++;
						continue;
					}
				}
				else
				if( (G[i]-dist1[j])%incycle1==0 )
				{
					cnt++;
					continue;
				}	
			}
			if(G[i]>=dist2[j])
			{
				if(incycle2==0)
				{
					if(G[i]==dist2[j])
						cnt++;
				}
				else
				if( (G[i]-dist2[j])%incycle2==0 )
					cnt++;
			}
		}
		answer(cnt);
	}
	/*
	for(int i=0;i<2*N;i++)
	{
		fprintf(stderr,"\n%d",revdest[i].size());
		for(int j=0;j<revdest[i].size();j++)
			fprintf(stderr," %d",revdest[i][j]);
	}
	*/
	return;
}

Compilation message

garden.cpp: In function 'void dfs1(int, int)':
garden.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int x=0;x<revdest[i].size();x++)
              ~^~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void dfs2(int, int)':
garden.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int x=0;x<revdest[i].size();x++)
              ~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 11116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 11116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 11116 KB Output isn't correct
2 Halted 0 ms 0 KB -