Submission #519509

#	Time	Username	Problem	Language	Result	Execution time	Memory
519509		AdamGS	Tropical Garden (IOI11_garden)	C++17	100 / 100	97 ms	19244 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=3e5+7, INF=1e9+7;
int nxt[LIM], odl[LIM], cnt[LIM], ile[LIM][2], ans[LIM][2], cykl[2], n;
vector<int>V[LIM];
void sortuj() {
	int ma=0, ilei=0;
	rep(i, n) {
		if(odl[i]==INF) ++ilei;
		else ma=max(ma, odl[i]);
	}
	rep(i, n) if(odl[i]<INF) ++cnt[odl[i]];
	int l=0;
	for(int i=0; cnt[ma]; ++i) {
		while(!cnt[l]) ++l;
		odl[i]=l;
		--cnt[l];
	}
	for(int i=n-1; ilei; --i, --ilei) odl[i]=INF;
}
void solve(int x, int r) {
	cykl[r]=INF;
	rep(i, 2*n) odl[i]=INF;
	odl[x]=0;
	queue<int>q;
	q.push(x);
	while(!q.empty()) {
		int p=q.front(); q.pop();
		for(auto i : V[p]) if(odl[i]>odl[p]+1) {
			odl[i]=odl[p]+1;
			q.push(i);
		}
		for(auto i : V[p]) if(i==x) cykl[r]=odl[p]+1;
	}
	sortuj();
	int l=0;
	rep(i, LIM) {
		int s=l;
		while(s<n && odl[s]==i) {
			++ans[i][r];
			++s;
		}
		if(cykl[r]<INF) {
			ans[i][r]+=ile[i%cykl[r]][r];
		}
		while(l<n && odl[l]==i) {
			++ile[i%cykl[r]][r];
			++l;
		}
	}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	n=N;
	rep(i, 2*n) nxt[i]=-1;
	rep(i, M) {
		int p1=R[i][1], p2=R[i][0];
		if(nxt[R[i][1]]==-1) p1+=n;
		if(nxt[R[i][0]]==-1) p2+=n;
		if(nxt[R[i][0]]==-1) nxt[R[i][0]]=p1;
		else if(nxt[R[i][0]+n]==-1) nxt[R[i][0]+n]=p1;
		if(nxt[R[i][1]]==-1) nxt[R[i][1]]=p2;
		else if(nxt[R[i][1]+n]==-1) nxt[R[i][1]+n]=p2;
	}
	rep(i, n) if(nxt[i]!=-1 && nxt[n+i]==-1) nxt[n+i]=nxt[i];
	rep(i, 2*n) if(nxt[i]!=-1) V[nxt[i]].pb(i);
	solve(P, 0);
	solve(P+n, 1);
	rep(i, Q) {
		if(G[i]<LIM) answer(ans[G[i]][0]+ans[G[i]][1]);
		else {
			int x=0;
			if(cykl[0]<INF) x+=ile[G[i]%cykl[0]][0];
			if(cykl[1]<INF) x+=ile[G[i]%cykl[1]][1];
			answer(x);
		}
	}
}

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