Submission #351832

#	Time	Username	Problem	Language	Result	Execution time	Memory
351832		juggernaut	Tropical Garden (IOI11_garden)	C++17	69 / 100	5062 ms	39764 KiB

garden

#pragma GCC optimize("O2,unroll-loops")
#include"garden.h"
#include"gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
int up[30][300005],cnt[300005];
void count_routes(int n,int m,int P,int R[][2],int Q,int G[]){
	memset(up,-1,sizeof up);
	for(int i=0;i<m;i++){
		int f=R[i][0],t=R[i][1];
		if(cnt[f]<2)up[0][(f<<1)+cnt[f]]=(t<<1)+(cnt[t]==0);
		if(cnt[t]<2)up[0][(t<<1)+cnt[t]]=(f<<1)+(cnt[f]==0);
		cnt[f]++,cnt[t]++;
	}
	for(int i=0;i<(n<<1);i++)if(up[0][i]<0)up[0][i]=up[0][i^1];
	for(int i=1;i<30;i++)
		for(int j=0;j<(n<<1);j++)
			up[i][j]=up[i-1][up[i-1][j]];
	for(int I=0;I<Q;I++){
		int ans=0;
		for(int i=0;i<(n<<1);i+=2)cnt[i]=i;
		for(int i=0;i<30;i++)
			if((G[I]>>i)&1)
			for(int j=0;j<(n<<1);j+=2)
				cnt[j]=up[i][cnt[j]];
		for(int i=0;i<(n<<1);i+=2)ans+=cnt[i]==(P<<1)||cnt[i]==(P<<1|1);
		answer(ans);
	}
}

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