Submission #29476

#	Time	Username	Problem	Language	Result	Execution time	Memory
29476		inqr	Tropical Garden (IOI11_garden)	C++14	100 / 100	2574 ms	34468 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rt insert
#define st first
#define nd second
using namespace std;
vector < int > ed[150005];
vector < pair < int , int > > r[2][150005];
vector < int > p[2];
int cycle1=-1,cycle2=-1;
void dfs(pair<int,int> vn,int rn,pair<int,int> &orv){
	//printf("vn = %d %d rn=%d orv= %d %d\n",vn.st,vn.nd,rn,orv.st,orv.nd);
	if(vn==orv&&rn!=0)
		if(orv.nd==0){cycle1=rn;return;}
		else {cycle2=rn;return;}
	if(vn.nd==0)
		if(orv.nd==0)p[0][vn.st]=rn;
		else p[1][vn.st]=rn;
	if(vn.nd==0)
		for(int i=0;i<r[0][vn.st].size();i++)
			dfs(r[0][vn.st][i],rn+1,orv);
	else
		for(int i=0;i<r[1][vn.st].size();i++)
			dfs(r[1][vn.st][i],rn+1,orv);
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	for(int i=0;i<M;i++){ed[R[i][0]].pb(R[i][1]);ed[R[i][1]].pb(R[i][0]);}
	for(int i=0;i<2;i++){p[i].resize(150005);fill(p[i].begin(),p[i].end(),-1);}
	for(int i=0;i<N;i++){
		if(ed[ed[i][0]][0]!=i) r[0][ed[i][0]].pb(mp(i,0)); // a 0 dan b 0
		if(ed[ed[i][0]][0]==i) r[1][ed[i][0]].pb(mp(i,0)); // a 0 dan b 1
		if(ed[i].size()>=2){
			if(ed[ed[i][1]][0]!=i) r[0][ed[i][1]].pb(mp(i,1)); // a 1 den b 0
			else if(ed[ed[i][1]][0]==i) r[1][ed[i][1]].pb(mp(i,1)); // a 1 den b 1
		}
		else{
			if(ed[ed[i][0]][0]!=i) r[0][ed[i][0]].pb(mp(i,1)); // a 0 dan b 0
			if(ed[ed[i][0]][0]==i) r[1][ed[i][0]].pb(mp(i,1)); // a 0 dan b 1
		}
	}
	pair<int,int>orv1=mp(P,0),orv2=mp(P,1);
	dfs(orv1,0,orv1);
	dfs(orv2,0,orv2);
	for(int i=0;i<Q;i++){
		int ans=0;
		for(int j=0;j<N;j++){
			//if(p[0][j]==G[i])ans++;
			if(p[0][j]!=-1 and cycle1!=-1 and (G[i]-p[0][j])%cycle1==0 and G[i]-p[0][j]>=0)ans++;
			else if(p[0][j]!=-1 and cycle1==-1 and p[0][j]==G[i])ans++;
			//if(p[1][j]==G[i])ans++;
			if(p[1][j]!=-1 and cycle2!=-1 and (G[i]-p[1][j])%cycle2==0 and G[i]-p[1][j]>=0)ans++;
			else if(p[1][j]!=-1 and cycle2==-1 and p[1][j]==G[i])ans++;
		}
		answer(ans);
	}
}

Compilation message (stderr)

garden.cpp: In function 'void dfs(std::pair<int, int>, int, std::pair<int, int>&)':
garden.cpp:16:4: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  if(vn==orv&&rn!=0)
    ^
garden.cpp:19:4: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  if(vn.nd==0)
    ^
garden.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<r[0][vn.st].size();i++)
               ~^~~~~~~~~~~~~~~~~~~
garden.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<r[1][vn.st].size();i++)
               ~^~~~~~~~~~~~~~~~~~~

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