oj.uz

Submission #986312

# Submission time Handle Problem Language Result Execution time Memory
986312 2024-05-20T09:54:37 Z Pyqe Tropical Garden (IOI11_garden) C++17
100 / 100
 89 ms 54032 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27228 KB Output is correct
2 Correct 8 ms 27228 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 7 ms 27072 KB Output is correct
5 Correct 6 ms 27292 KB Output is correct
6 Correct 6 ms 27484 KB Output is correct
7 Correct 6 ms 27252 KB Output is correct
8 Correct 6 ms 27228 KB Output is correct
9 Correct 7 ms 27324 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27228 KB Output is correct
2 Correct 8 ms 27228 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 7 ms 27072 KB Output is correct
5 Correct 6 ms 27292 KB Output is correct
6 Correct 6 ms 27484 KB Output is correct
7 Correct 6 ms 27252 KB Output is correct
8 Correct 6 ms 27228 KB Output is correct
9 Correct 7 ms 27324 KB Output is correct
10 Correct 6 ms 27480 KB Output is correct
11 Correct 14 ms 29244 KB Output is correct
12 Correct 23 ms 30344 KB Output is correct
13 Correct 44 ms 46676 KB Output is correct
14 Correct 63 ms 39584 KB Output is correct
15 Correct 74 ms 39872 KB Output is correct
16 Correct 52 ms 37072 KB Output is correct
17 Correct 47 ms 35512 KB Output is correct
18 Correct 21 ms 30432 KB Output is correct
19 Correct 62 ms 39580 KB Output is correct
20 Correct 89 ms 39244 KB Output is correct
21 Correct 56 ms 37072 KB Output is correct
22 Correct 48 ms 35788 KB Output is correct
23 Correct 62 ms 41168 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27228 KB Output is correct
2 Correct 8 ms 27228 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 7 ms 27072 KB Output is correct
5 Correct 6 ms 27292 KB Output is correct
6 Correct 6 ms 27484 KB Output is correct
7 Correct 6 ms 27252 KB Output is correct
8 Correct 6 ms 27228 KB Output is correct
9 Correct 7 ms 27324 KB Output is correct
10 Correct 6 ms 27480 KB Output is correct
11 Correct 14 ms 29244 KB Output is correct
12 Correct 23 ms 30344 KB Output is correct
13 Correct 44 ms 46676 KB Output is correct
14 Correct 63 ms 39584 KB Output is correct
15 Correct 74 ms 39872 KB Output is correct
16 Correct 52 ms 37072 KB Output is correct
17 Correct 47 ms 35512 KB Output is correct
18 Correct 21 ms 30432 KB Output is correct
19 Correct 62 ms 39580 KB Output is correct
20 Correct 89 ms 39244 KB Output is correct
21 Correct 56 ms 37072 KB Output is correct
22 Correct 48 ms 35788 KB Output is correct
23 Correct 62 ms 41168 KB Output is correct
24 Correct 6 ms 27228 KB Output is correct
25 Correct 13 ms 29144 KB Output is correct
26 Correct 23 ms 30432 KB Output is correct
27 Correct 44 ms 46932 KB Output is correct
28 Correct 62 ms 39572 KB Output is correct
29 Correct 72 ms 38924 KB Output is correct
30 Correct 51 ms 37072 KB Output is correct
31 Correct 48 ms 35524 KB Output is correct
32 Correct 23 ms 30436 KB Output is correct
33 Correct 61 ms 39632 KB Output is correct
34 Correct 71 ms 39884 KB Output is correct
35 Correct 56 ms 36980 KB Output is correct
36 Correct 49 ms 35572 KB Output is correct
37 Correct 62 ms 41104 KB Output is correct
38 Correct 70 ms 54032 KB Output is correct