Submission #49992

#	Time	Username	Problem	Language	Result	Execution time	Memory
49992		Diuven	Tropical Garden (IOI11_garden)	C++11	100 / 100	4914 ms	14192 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=300010, inf=2e9;

int n, nxt[MX], Q1, Q2; // in, out

void debug(){
	for(int i=0; i<n; i++)
		cout<<nxt[i]<<' ';
	cout<<"\n\n";
}


int fir[MX], scd[MX];
void init(int V, int E, int P, int R[][2]){
	fill(fir, fir+n, -1);
	fill(scd, scd+n, -1);
	// u->v: 0, v->u: 1
	for(int i=0; i<E; i++){
		int u=R[i][0], v=R[i][1];
		if(fir[u]<0) fir[u]=2*i;
		else if(scd[u]<0) scd[u]=2*i;
		if(fir[v]<0) fir[v]=2*i+1;
		else if(scd[v]<0) scd[v]=2*i+1;
	}
	for(int i=0; i<E; i++){
		int u=R[i][0], v=R[i][1];
		// u->v, v->u
		if(fir[v]==2*i+1 && scd[v]>=0) nxt[2*i]=scd[v];
		else nxt[2*i]=fir[v];
		if(fir[u]==2*i && scd[u]>=0) nxt[2*i+1]=scd[u];
		else nxt[2*i+1]=fir[u];
	}
	Q1=fir[P]+(fir[P]%2==0 ? 1 : -1), Q2=fir[P];
}

int D1[MX], D2[MX], cyc1, cyc2;

bool vis1[MX], vis2[MX], vis3[MX];

int dep[MX], now;

void dfs1(int v){
	vis1[v]=true; dep[v]=++now;
	if(v==Q1) D1[v]=0;
	int x=nxt[v];
	if(!vis1[x]) dfs1(x);
	if(x==Q1) cyc1=dep[v]-dep[x]+1;
	D1[v]=min(D1[v], D1[x]+1);
}
void dfs2(int v){
	vis2[v]=true; dep[v]=++now;
	if(v==Q2) D2[v]=0;
	int x=nxt[v];
	if(!vis2[x]) dfs2(x);
	if(x==Q2) cyc2=dep[v]-dep[x]+1;
	D2[v]=min(D2[v], D2[x]+1);
}

void dfs3(int v){
	vis3[v]=true;
	int x=nxt[v];
	if(!vis3[x]) dfs3(x);
	D1[v]=min(D1[v], (D1[x]==inf ? inf : D1[x]+1)); 
	D2[v]=min(D2[v], (D2[x]==inf ? inf : D2[x]+1)); 
}

void prec(){
	fill(D1, D1+n, inf); D1[Q1]=0;
	fill(D2, D2+n, inf); D2[Q2]=0;
	cyc1=cyc2=0;
	dfs1(Q1);
	dfs2(Q2);
	for(int i=0; i<n; i++)
		vis3[i]=vis1[i]&&vis2[i];
	for(int i=0; i<n; i++){
		if(vis3[i]) continue;
		dfs3(i);
	}
}

bool valid(int d, int k, int c){
	if(d>=inf/2) return false;
	return (c==0 && k==d) || (c!=0 && d<=k && (k-d)%c==0);
}

int solve(int k, int V){
	int ans=0;
	for(int i=0; i<V; i++){
		int e=fir[i];
		ans+=(valid(D1[e]+1, k, cyc1) || valid(D2[e], k, cyc2));
	}
	return ans;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	n=2*M;

	init(N,M,P,R);
	prec();

	for(int i=0; i<Q; i++)
		answer(solve(G[i], N));
}

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