Submission #61764

#	Time	Username	Problem	Language	Result	Execution time	Memory
61764		CaQtiml	Tropical Garden (IOI11_garden)	C++14	Compilation error	0 ms	0 KiB

garden

#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>
#include <cstring>
#include <cstdio>

#define QMAX 2010
#define NMAX 150010
#define INF (1e9)

using namespace std;

int best[NMAX][2];
int deg[NMAX];

int out[NMAX*2];
vector<int> in[NMAX*2];

int dist[2][NMAX*2];

int N,M,P,len[2],src;

int visited[NMAX*2];

void dfs(int v){
	visited[v] = 1;

	int i,u;

	for(i = 0; i < (int)in[v].size(); ++i){
		u = in[v][i];
		if(visited[u]){
			assert(len[src] >= INF);
			len[src] = dist[src][v]-dist[src][u]+1;
			continue;
		}
		dist[src][u] = dist[src][v] + 1;
		dfs(u);
	}
}

int order[NMAX];
pair<int,int> queries[QMAX];
int ct[NMAX*2];
int ans[QMAX];

int Q;

int compare(int a, int b){
	return dist[src][a] < dist[src][b];
}

void init(){
	int i,v,k;

	memset(out,-1,sizeof(out));

	for(i = 0; i < N; ++i){
		v = i;
		for(k = 0; k < deg[i]; ++k,v+=N){
			out[v] = best[i][k];
		}
	}

	for(i = 0; i < N*2; ++i){
		if(out[i] < 0)	continue;

		v = out[i];
		if(deg[v] >= 2 && (i%N) == best[v][0]) v += N;
		in[v].push_back(i);
		out[i] = v;

	}

	for(i = 0; i < N*2; ++i) dist[0][i] = dist[1][i] = INF;
	len[0] = len[1] = INF+1;

	for(i = 0; i < N; ++i){
		order[i] = i;
	}

	for(;src<2;++src){
		memset(visited,0,sizeof(visited));
		dist[src][P+src*N] = 0;
		dfs(P+src*N);
	}

	sort(queries,queries+Q);
}

void compute(){
	int i,k,v;


	for(src=0; src < 2; ++src){
		sort(order,order+N,compare);
		k = 0;
		memset(ct,0,sizeof(ct));

		for(i = 0; i < Q; ++i){
			while(k < N && dist[src][order[k]] <= queries[i].first){
				v = dist[src][order[k++]];
				if(v >= INF) continue;
				ct[v%len[src]]++;
			}

			ans[queries[i].second] += (queries[i].first%len[src]) > 2*N ? 0 : ct[queries[i].first%len[src]];
		}
	}

}

int main(){
	int i,v,u;

	scanf("%d%d%d",&N,&M,&P);

	for(i =0; i < M; ++i){
		scanf("%d%d",&u,&v);
		if(deg[v] < 2) best[v][deg[v]++] = u;
		if(deg[u] < 2) best[u][deg[u]++] = v;
	}

	scanf("%d",&Q);

	for(i = 0; i < Q; ++i){
		scanf("%d",&queries[i].first);
		queries[i].second = i;
	}

	init();
	compute();

	for(i =0 ; i < Q; ++i){
		printf("%d ",ans[i]);
	}
	printf("\n");

	return 0;
}

Compilation message (stderr)

garden.cpp: In function 'int main()':
garden.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&N,&M,&P);
  ~~~~~^~~~~~~~~~~~~~~~~~~
garden.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~
garden.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&Q);
  ~~~~~^~~~~~~~~
garden.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&queries[i].first);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccRFqnz7.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cciKI3eq.o:garden.cpp:(.text.startup+0x0): first defined here
/tmp/ccRFqnz7.o: In function `main':
grader.cpp:(.text.startup+0x38): undefined reference to `count_routes(int, int, int, int (*) [2], int, int*)'
collect2: error: ld returned 1 exit status