Submission #64784

#	Time	Username	Problem	Language	Result	Execution time	Memory
64784		TadijaSebez	Tropical Garden (IOI11_garden)	C++11	100 / 100	139 ms	27320 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
const int N=150050;
const int M=2*N;
//---------------------//
/*
void answer(int x){ printf("%i\n",x);}
*/
//---------------------//
int go[M],deg[M],dep[M],cnt[M],sol[M];
vector<int> E[M];
pair<int,int> Qs[M];
void DFS(int u, int d)
{
	dep[u]=d;
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(dep[v]==-1) DFS(v,d+1);
	}
}
bool was[M];
int Cycle(int u, int n)
{
	int i,ret=0;
	for(i=0;i<n*2;i++) was[i]=0;
	for(i=u;!was[i];i=go[i]) was[i]=1,ret++;
	if(i==u) return ret;
	return 0;
}
void count_routes(int n, int m, int p, int r[][2], int q, int k[])
{
	int i,j,cyc;
	for(i=0;i<q;i++) Qs[i].first=k[i],Qs[i].second=i;
	sort(Qs,Qs+q);
	for(i=0;i<n*2;i++) go[i]=-1;
	for(i=0;i<m;i++)
	{
		int u=r[i][0],v=r[i][1];
		int f1=0,f2=0;
		if(!~go[u<<1]) f1=1;
		else if(!~go[u<<1|1]) f1=2;
		if(!~go[v<<1]) f2=1;
		else if(!~go[v<<1|1]) f2=2;
		if(f1==1) go[u<<1]=f2==1?v<<1|1:v<<1;
		if(f1==2) go[u<<1|1]=f2==1?v<<1|1:v<<1;
		if(f2==1) go[v<<1]=f1==1?u<<1|1:u<<1;
		if(f2==2) go[v<<1|1]=f1==1?u<<1|1:u<<1;
	}
	for(i=0;i<n*2;i++) if(!~go[i]) go[i]=go[i^1];
	for(i=0;i<n*2;i++) E[go[i]].pb(i);//,printf("%i -> %i\n",go[i],i);
	for(i=0;i<n*2;i++) dep[i]=-1;
	for(i=0;i<=n*2;i++) cnt[i]=0;
	DFS(p<<1,0);
	cyc=Cycle(p<<1,n);
	//printf("-> %i\n",cyc);
	if(!cyc)
	{
		for(i=0;i<n*2;i+=2) if(dep[i]>=0) cnt[dep[i]]++;
		for(i=0;i<q;i++) if(k[i]<=2*n) sol[i]+=cnt[k[i]];
	}
	else
	{
		vector<int> Ds;
		for(i=0;i<n*2;i+=2) if(dep[i]>=0) Ds.pb(dep[i]);
		sort(Ds.begin(),Ds.end());
		j=0;
		for(i=0;i<q;i++)
		{
			while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++;
			sol[Qs[i].second]+=cnt[Qs[i].first%cyc];
		}
	}
	//for(i=0;i<q;i++) printf("%i ",sol[i]);printf("\n");
	for(i=0;i<n*2;i++) dep[i]=-1;
	for(i=0;i<=n*2;i++) cnt[i]=0;
	DFS(p<<1|1,0);
	cyc=Cycle(p<<1|1,n);
	//printf("-> %i\n",cyc);
	if(!cyc)
	{
		for(i=0;i<n*2;i+=2) if(dep[i]>=0) cnt[dep[i]]++;
		for(i=0;i<q;i++) if(k[i]<=2*n) sol[i]+=cnt[k[i]];
	}
	else
	{
		vector<int> Ds;
		for(i=0;i<n*2;i+=2) if(dep[i]>=0) Ds.pb(dep[i]);
		sort(Ds.begin(),Ds.end());
		j=0;
		for(i=0;i<q;i++)
		{
			while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++;
			sol[Qs[i].second]+=cnt[Qs[i].first%cyc];
		}
	}
	for(i=0;i<q;i++) answer(sol[i]);
}
/*int go[M],lo[M],dep[M];
vector<int> E[M];
void DFS(int u, int p)
{
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		dep[v]=dep[u]+1;
		if(v!=p) DFS(v,p);
	}
}
pair<int,int> Qs[N];
int cnt[M],sol[N];
void count_routes(int n, int m, int p, int r[][2], int q, int k[])
{
	int i,j;
	for(i=0;i<q;i++) Qs[i].first=k[i],Qs[i].second=i;
	sort(Qs,Qs+q);
	for(i=0;i<n*2;i++) lo[i]=-1;
	for(i=0;i<n*2;i++) go[i]=-1;
	for(i=0;i<m;i++)
	{
		if(lo[r[i][0]<<1]==-1) lo[r[i][0]<<1]=i;
		else if(lo[r[i][0]<<1|1]==-1) lo[r[i][0]<<1|1]=i;
		if(lo[r[i][1]<<1]==-1) lo[r[i][1]<<1]=i;
		else if(lo[r[i][1]<<1|1]==-1) lo[r[i][1]<<1|1]=i;
	}
	for(i=0;i<n*2;i++)
	{
		int x=lo[i];
		if(lo[i]==-1) x=lo[i^1];
		int v=r[x][0];
		if(v==i/2) v=r[x][1];
		if(x==lo[v<<1]) go[i]=v<<1|1;
		else go[i]=v<<1;
	}
	for(i=0;i<2*n;i++)
	{
		E[go[i]].pb(i);
		//printf("%i -> %i\n",go[i],i);
		dep[i]=-1;
	}
	dep[p<<1]=0;
	DFS(p<<1,p<<1);
	if(dep[p<<1]==0)
	{
		for(i=0;i<2*n;i+=2) if(dep[i]>=0) cnt[dep[i]]++;
		for(i=0;i<q;i++) if(k[i]<M) sol[i]+=cnt[k[i]];
		for(i=0;i<2*n;i+=2) if(dep[i]>=0) cnt[dep[i]]--;
	}
	else
	{
		int cyc=dep[p<<1];
		dep[p<<1]=0;
		j=0;
		vector<int> Ds;
		for(i=0;i<2*n;i+=2) if(dep[i]>=0) Ds.pb(dep[i]);
		sort(Ds.begin(),Ds.end());
		for(i=0;i<q;i++)
		{
			while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++;
			sol[Qs[i].second]+=cnt[Qs[i].first%cyc];
		}
		for(i=0;i<cyc;i++) cnt[i]=0;
	}
	for(i=0;i<2*n;i++) dep[i]=-1;
	dep[p<<1|1]=0;
	DFS(p<<1|1,p<<1|1);
	if(dep[p<<1|1]==0)
	{
		for(i=0;i<2*n;i+=2) if(dep[i]>=0) cnt[dep[i]]++;
		for(i=0;i<q;i++) if(k[i]<M) sol[i]+=cnt[k[i]];
		for(i=0;i<2*n;i+=2) if(dep[i]>=0) cnt[dep[i]]--;
	}
	else
	{
		int cyc=dep[p<<1|1];
		dep[p<<1|1]=0;
		//printf("%i :D\n",cyc);
		j=0;
		vector<int> Ds;
		for(i=0;i<2*n;i+=2) if(dep[i]>=0) Ds.pb(dep[i]);
		sort(Ds.begin(),Ds.end());
		for(i=0;i<q;i++)
		{
			while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++;
			sol[Qs[i].second]+=cnt[Qs[i].first%cyc];
		}
		for(i=0;i<cyc;i++) cnt[i]=0;
	}
	for(i=0;i<q;i++) answer(sol[i]);
}*/
//---------------------//
/*
int r[N][2],k[N];
int main()
{
	int n,m,p,q,i;
	scanf("%i %i %i",&n,&m,&p);
	for(i=0;i<m;i++) scanf("%i %i",&r[i][0],&r[i][1]);
	scanf("%i",&q);
	for(i=0;i<q;i++) scanf("%i",&k[i]);
	count_routes(n,m,p,r,q,k);
	return 0;
}
*/
//---------------------//

Compilation message (stderr)

garden.cpp: In function 'void DFS(int, int)':
garden.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++)
              ~^~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:75:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++;
          ~^~~~~~~~~~
garden.cpp:98:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++;
          ~^~~~~~~~~~

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31