Submission #986312

#	Time	Username	Problem	Language	Result	Execution time	Memory
986312		Pyqe	Tropical Garden (IOI11_garden)	C++17	100 / 100	89 ms	54032 KiB

garden

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

using namespace std;

long long n,rt,cr,pr[300069],nr[300069],cl[2],inf=1e18;
bitset<300069> vtd;
vector<long long> al[300069],vl[2][300069];

void dfs(long long x)
{
	long long i,sz=al[x].size(),l;
	
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		if(l!=n*cr+rt)
		{
			nr[l]=nr[x]+1;
			dfs(l);
		}
		else
		{
			cl[cr]=nr[x]+1;
		}
	}
}

void count_routes(int on,int m,int rtt,int ed[][2],int t,int qq[])
{
	long long rr,i,ii,iii,k,l,z;
	
	n=on;
	rt=rtt;
	for(i=0;i<m;i++)
	{
		k=ed[i][0];
		l=ed[i][1];
		for(ii=0;ii<2;ii++)
		{
			for(iii=0;iii<2;iii++)
			{
				if(!vtd[n*iii+k])
				{
					pr[n*iii+k]=n*!vtd[l]+l;
					break;
				}
			}
			swap(k,l);
		}
		for(ii=0;ii<2;ii++)
		{
			vtd[n*vtd[k]+k]=1;
			swap(k,l);
		}
	}
	for(i=0;i<n*2;i++)
	{
		if(!vtd[i])
		{
			pr[i]=pr[i-n];
		}
		al[pr[i]].push_back(i);
	}
	for(ii=0;ii<2;ii++)
	{
		cr=ii;
		for(i=0;i<n*2;i++)
		{
			nr[i]=inf;
		}
		cl[ii]=inf;
		nr[n*ii+rt]=0;
		dfs(n*ii+rt);
		for(i=0;i<n;i++)
		{
			vl[ii][nr[i]%cl[ii]].push_back(nr[i]);
		}
		for(i=0;i<min(cl[ii],n);i++)
		{
			sort(vl[ii][i].begin(),vl[ii][i].end());
		}
	}
	for(rr=0;rr<t;rr++)
	{
		z=0;
		for(ii=0;ii<2;ii++)
		{
			k=qq[rr]%cl[ii];
			if(k<n)
			{
				z+=upper_bound(vl[ii][k].begin(),vl[ii][k].end(),qq[rr])-vl[ii][k].begin();
			}
		}
		answer(z);
	}
}

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