Submission #94655

#	Time	Username	Problem	Language	Result	Execution time	Memory
94655		andy627	Tropical Garden (IOI11_garden)	C++17	49 / 100	23 ms	19984 KiB

garden

#include "gardenlib.h"

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;

int n;
vector<int> edge[155555];
vector<int> gph[333333],rev[333333];

int cyc;
int dfn[333333];

int ans1[333333],ans2[333333];
bool is_gone[333333];

void dfs1(int v,int p,int dist){
	if(dfn[v]){
		cyc=dist-dfn[v];
		return;
	}

	dfn[v]=dist;
	for(int u:gph[v]){
		if(u==p) continue;
		dfs1(u,v,dist+1);
	}
}

void dfs2(int v,int p,int dist){
	//printf("%d %d!\n",v,dist);

	is_gone[v]=1;
	if(v%2==0){
		for(int i=dist;i<=(n<<1);i+=cyc) ans1[i]++;
		ans2[dist%cyc]++;
	}

	for(int u:rev[v]){
		if(u==p || is_gone[u]) continue;
		dfs2(u,v,dist+1);
	}
	is_gone[v]=0;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	n=N;
	for(int i=0;i<M;i++){
		edge[R[i][0]].push_back(R[i][1]);
		edge[R[i][1]].push_back(R[i][0]);
	}

	for(int i=0;i<N;i++){
		if(edge[i].size()>2) edge[i].resize(2);
		if(edge[i].size()==1) edge[i].push_back(edge[i][0]);

		if(edge[edge[i][0]][0]==i){
			gph[i<<1].push_back(edge[i][0]<<1|1);
			rev[edge[i][0]<<1|1].push_back(i<<1);
		}
		else{
			gph[i<<1].push_back(edge[i][0]<<1);
			rev[edge[i][0]<<1].push_back(i<<1);
		}

		if(edge[edge[i][1]][0]==i){
			gph[i<<1|1].push_back(edge[i][1]<<1|1);
			rev[edge[i][1]<<1|1].push_back(i<<1|1);
		}
		else{
			gph[i<<1|1].push_back(edge[i][1]<<1);
			rev[edge[i][1]<<1].push_back(i<<1|1);
		}
	}

	//for(int i=0;i<(N<<1);i++){
	//	printf("#%d : ",i); 
	//	for(int j:rev[i]) printf("%d ",j);
	//	printf("\n");
	//}


	dfs1(0,0,1);
	//printf("cyc%d\n",cyc);
	dfs2(P<<1,P<<1,0);
	dfs2(P<<1|1,P<<1|1,0);

	//for(int i=0;i<(N<<1);i++) printf("%d ",ans1[i]); printf("\n");
	//for(int i=0;i<cyc;i++) printf("%d ",ans2[i]); printf("\n");
	//printf("%d\n",cyc);

	//for(int i=0;i<(N<<1);i++) printf("%d ",ans1[i]); printf("\n");
	//for(int i=0;i<cyc;i++) printf("%d ",ans2[i]); printf("\n");

	for(int i=0;i<Q;i++){
		if(G[i]>(N<<1)) answer(ans2[G[i]%cyc]);
		else answer(ans1[G[i]]);
	}

	return;
}

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