Submission #402457

#	Time	Username	Problem	Language	Result	Execution time	Memory
402457		Jasiekstrz	Tropical Garden (IOI11_garden)	C++17	100 / 100	213 ms	158856 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=15e5;
// came in: 0 - best, 1 - not best
vector<pair<int,int>> in[NN][2];
int anss[NN+10];
int out[NN+10][2];
vector<int> cnt[2*NN+10];
bool vis[NN+10][2];
int dd[NN+10][2];
bool end_type(int x,int y)
{
	return (x!=out[y][1]);
}
pair<int,int> go(pair<int,int> x)
{
	int y=out[x.fi][x.se];
	return {y,end_type(x.fi,y)};
}
void add_edge(int x,int y)
{
	if(out[x][1]==-1)
		out[x][1]=y;
	else if(out[x][0]==-1)
		out[x][0]=y;
	return;
}
void reverse_edge(int x,int t,int y)
{
	in[y][end_type(x,y)].push_back({x,t});
	return;
}
int cycle(int P,int t,int N)
{
	for(int i=0;i<N;i++)
		vis[i][0]=vis[i][1]=false;
	int ans=0;
	pair<int,int> x={P,t};
	for(;!vis[x.fi][x.se];ans++,x=go(x))
	{
		vis[x.fi][x.se]=true;
	}
	if(x==make_pair(P,t))
		return ans;
	return 10*N;
}
void paths(int P,int t,int N,int l)
{
	for(int i=0;i<l;i++)
		cnt[i].clear();
	for(int i=0;i<N;i++)
		vis[i][0]=vis[i][1]=false;
	vis[P][t]=true;
	dd[P][t]=0;
	queue<pair<int,int>> qq;
	qq.push({P,t});
	while(!qq.empty())
	{
		auto v=qq.front();
		qq.pop();
		if(v.se==1)
			cnt[dd[v.fi][v.se]%l].push_back(dd[v.fi][v.se]);
		for(auto y:in[v.fi][v.se])
		{
			if(!vis[y.fi][y.se])
			{
				vis[y.fi][y.se]=true;
				dd[y.fi][y.se]=dd[v.fi][v.se]+1;
				qq.push(y);
			}
		}
	}
	return;
}
int cnt_paths(int id,int mx)
{
	if(cnt[id].empty() || cnt[id][0]>mx)
		return 0;
	int bg=0,en=cnt[id].size()-1;
	while(bg<en)
	{
		int mid=(bg+en+1)/2;
		if(cnt[id][mid]<=mx)
			bg=mid;
		else
			en=mid-1;
	}
	return bg+1;
}
void count_routes(int N,int M,int P,int R[][2],int Q,int G[])
{
	for(int i=0;i<N;i++)
		out[i][0]=out[i][1]=-1;
	for(int i=0;i<M;i++)
	{
		add_edge(R[i][0],R[i][1]);
		add_edge(R[i][1],R[i][0]);
	}
	for(int i=0;i<N;i++)
	{
		if(out[i][0]==-1)
			out[i][0]=out[i][1];
		reverse_edge(i,0,out[i][0]);
		reverse_edge(i,1,out[i][1]);
	}	
	for(int t:{0,1})
	{
		int l=cycle(P,t,N);
		paths(P,t,N,l);
		for(int i=0;i<Q;i++)
		{
			if(l==10*N && G[i]>l)
				continue;
			anss[i]+=cnt_paths(G[i]%l,G[i]);
		}
	}
	for(int i=0;i<Q;i++)
		answer(anss[i]);
	return;
}

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