Submission #580904

#	Time	Username	Problem	Language	Result	Execution time	Memory
580904		benson1029	Tropical Garden (IOI11_garden)	C++14	49 / 100	178 ms	75400 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;

vector< int > edg[300005];

int n;
int nxt[300005];
vector<int> p[300005];
bool vis1[300005], vis2[300005];
int dis1[300005], dis2[300005];
vector<int> ans1[300005], ans2[300005];
vector<int> cycle;
int mod1, mod2;

void rdfs1(int x, int dis) {
	if(x<n) ans1[dis%mod1].push_back(dis);
	for(int i:p[x]) {
		if(vis1[i]) continue;
		rdfs1(i, dis+1);
	}
}

void rdfs2(int x, int dis) {
	if(x<n) ans2[dis%mod2].push_back(dis);
	for(int i:p[x]) {
		if(vis2[i]) continue;
		rdfs2(i, dis+1);
	}
}

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++) {
		edg[R[i][0]].push_back(R[i][1]);
		edg[R[i][1]].push_back(R[i][0]);
	}
	for(int i=0; i<2*N; i++) {
		int dest;
		if(i<N) {
			dest = edg[i][0];
		}
		else {
			if(edg[i%N].size()==1) dest = -1;
			else dest = edg[i%N][1];
		}
		if(dest!=-1 && i%N == edg[dest][0] && edg[dest].size()>1) dest+=N;
		nxt[i] = dest;
		if(dest!=-1) p[dest].push_back(i);
	}
	int ptr = P;
	int tmp = 0;
	if(nxt[ptr] != -1) {
		while(!vis1[ptr]) {
			vis1[ptr] = true;
			dis1[ptr] = tmp;
			ptr = nxt[ptr];
			tmp++;
		}
		if(ptr != P) { // non-cyclic case
			for(int i=0; i<2*N; i++) vis1[i] = false;
			vis1[P] = true;
			mod1 = 2e9;
			rdfs1(P, 0);
		} else {
			mod1 = tmp;
			for(int i=0; i<2*N; i++) {
				if(vis1[i]) rdfs1(i, (mod1-dis1[i])%mod1);
			}
		}
	}

	ptr = P+n;
	tmp = 0;
	while(!vis2[ptr]) {
		vis2[ptr] = true;
		dis2[ptr] = tmp;
		ptr = nxt[ptr];
		tmp++;
	}
	if(ptr != P+n) {
		for(int i=0; i<2*N; i++) vis2[i] = false;
		vis2[P+n] = true;
		mod2 = 2e9;
		rdfs2(P+n, 0);
	} else {
		mod2 = tmp;
		for(int i=0; i<2*N; i++) {
			if(vis2[i]) rdfs2(i, (mod2-dis2[i])%mod2);
		}
	}

	for(int i=0; i<=2*n; i++) {
		sort(ans1[i].begin(), ans1[i].end());
		sort(ans2[i].begin(), ans2[i].end());
	}

	for(int i=0; i<Q; i++) {
		int g = G[i];
		int ans = 0;
		ans += upper_bound(ans1[g%mod1].begin(), ans1[g%mod1].end(), g) - ans1[g%mod1].begin();
		ans += upper_bound(ans2[g%mod2].begin(), ans2[g%mod2].end(), g) - ans2[g%mod2].begin();
		answer(ans);
	}
}

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