Submission #298862

#	Time	Username	Problem	Language	Result	Execution time	Memory
298862		AMO5	Tropical Garden (IOI11_garden)	C++17	100 / 100	149 ms	30072 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define eb emplace_back

const int mxn = 3e5+5;
vi adj[mxn];
int n,q,F[mxn],deg[mxn],vis[mxn],dist[mxn],D[mxn],Cnt[mxn],ans[2002];

struct query{
	int k,ind;
	query(int kk, int i){
		k=kk,ind=i;
	}
	bool operator < (const query &rhs)const{
		return k<rhs.k;
	}
};

vector<query>qq;

void add(int a, int b, int ind){
	if(vis[a]==ind){
		if(vis[b]!=ind||deg[b]==1)F[a]=b;
		else F[a]=b+n;
	}else if(F[a+n]==-1){
		if(vis[b]!=ind||deg[b]==1)F[a+n]=b;
		else F[a+n]=b+n;
	}
}

void dfs(int u, int d){
	dist[u]=d;
	for(int v:adj[u]){
		if(dist[v]==-1)dfs(v,d+1);
	}
}

void run(int st){
	for(int i=0; i<=2*n; i++){
		dist[i]=-1;
		vis[i]=0;
		Cnt[i]=0;
	}
	dfs(st,0);
	int cnt = 0;
	for(int i=0; i<n; i++){
		if(dist[i]!=-1){
			D[cnt++]=dist[i];
		}
	}
	sort(D,D+cnt);
	//calculate cycle size
	int c = 0;
	int now = st;
	while(!vis[now]){
		c++;
		vis[now]=1;
		now = F[now];
	}
	if(now!=st)c=1000000009;
	int ptr = 0;
	for(int i=0; i<q; i++){
		while(ptr<cnt&&D[ptr]<=qq[i].k){
			Cnt[D[ptr]%c]++;
			ptr++;
		}
		int md = qq[i].k%c;
		if(md>2*n)continue;
		ans[qq[i].ind]+=Cnt[md];
	}
	return;
}


void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	n=N,q=Q;
	int m=M;
	for(int i=0; i<q; i++){
		qq.eb(G[i],i);
	}
	sort(qq.begin(),qq.end());
	for(int i=0; i<m; i++){
		int u = R[i][0], v = R[i][1];
		deg[u]++,deg[v]++;
		if(!vis[u])vis[u]=i+1;
		if(!vis[v])vis[v]=i+1;
	}
	memset(F,-1,sizeof(F));
	for(int i=0; i<m; i++){
		int u = R[i][0], v = R[i][1];
		add(u,v,i+1);
		add(v,u,i+1);
	}
	for(int i=0; i<n; i++){
		adj[F[i]].eb(i);
		if(deg[i]>1)adj[F[i+n]].eb(i+n);
	}
	run(P);
	if(deg[P]>1)run(P+n);
	for(int i=0; i<q; i++)answer(ans[i]);
}

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