Submission #744660

#	Time	Username	Problem	Language	Result	Execution time	Memory
744660		CSQ31	Tropical Garden (IOI11_garden)	C++17	100 / 100	135 ms	55020 KiB

garden

#include "garden.h"
#include <bits/stdc++.h>
#include "gardenlib.h"
using namespace std;
const int MAXN = 4e5;
vector<int>g[MAXN],adj[MAXN];
int jump[MAXN],cycle[MAXN],col[MAXN],dist[MAXN],vis[MAXN],ans[MAXN];
void dfs(int v){
	col[v] = 1;
	if(col[jump[v]] ==1)cycle[v] = 1;
	else if(!col[jump[v]])dfs(jump[v]);
	col[v] = 2;
}
void dfs2(int v){
	vis[v] = 1;
	for(int x:adj[v]){
		if(!vis[x]){
			dist[x] = dist[v]+1;
			dfs2(x);
		}	
	}
	
}

void count_routes(int n, int m, int p, int r[][2], int q, int G[])
{
	for(int i=0;i<m;i++){
		g[r[i][0]].push_back(r[i][1]);
		g[r[i][1]].push_back(r[i][0]);
	}
	for(int i=0;i<n;i++){
		//2*i -> most beautiful route wasnt taken last turn
		//2*i+1 ->most beautiful route was taken
		int v = g[i][0];
		if(g[v][0] != i)jump[2*i] = 2*v;
		else jump[2*i] = 2*v+1;
		
		int s = g[i].size();
		if(s > 1)v = g[i][1];
		if(g[v][0] != i)jump[2*i+1] = 2*v;
		else jump[2*i+1] = 2*v+1; 
	}
	for(int i=0;i<2*n;i++){
		if(!col[i])dfs(i);
		if(cycle[i]){
			int v = jump[i];
			while(!cycle[v]){
				cycle[v] = 1;
				v = jump[v];
			}
		}
		adj[jump[i]].push_back(i);
	}
	//for(int i=0;i<2*n;i++)cout<<cycle[i]<<" ";
	//cout<<'\n';
	//for(int i=0;i<2*n;i++)cout<<jump[i]<<" ";
	//cout<<'\n';
	for(int i=0;i<2*n;i++){
		dist[i] = 1e9;
		vis[i] = 0;
	}
	dist[2*p] = 0;
	dfs2(2*p);
	if(!cycle[2*p]){
		
		vector<int>cnt(n+1,0);
		for(int i=0;i<n;i++){
			if(dist[2*i] != 1e9)cnt[dist[2*i]]++;
		}
		for(int i=0;i<q;i++){
			if(G[i]<=n)ans[i]+=cnt[G[i]];
		}
	}else{
		int len = 1;
		int v = jump[2*p];
		while(v != 2*p){
			len++;
			v = jump[v];
		}
		vector<vector<int>>mod(len);
		for(int i=0;i<n;i++){
			if(dist[2*i] != 1e9){
				int x = dist[2*i];
				mod[x%len].push_back(x);	
			}
		}
		for(int i=0;i<len;i++)sort(mod[i].begin(),mod[i].end());
		for(int i=0;i<q;i++){
			int rem = G[i]%len;
			if(mod[rem].empty())continue;
			int pt = upper_bound(mod[rem].begin(),mod[rem].end(),G[i]) - mod[rem].begin();
			ans[i]+=pt;
		}
	}
	for(int i=0;i<2*n;i++){
		dist[i] = 1e9;
		vis[i] = 0;
	}
	dist[2*p+1] = 0;
	dfs2(2*p+1);
	if(!cycle[2*p+1]){
		vector<int>cnt(n+1,0);
		for(int i=0;i<n;i++){
			if(dist[2*i] != 1e9)cnt[dist[2*i]]++;
		}
		for(int i=0;i<q;i++){
			if(G[i]<=n)ans[i]+=cnt[G[i]];
		}
	}else{
		int len = 1;
		int v = jump[2*p+1];
		while(v != 2*p+1){
			len++;
			v = jump[v];
		}
		vector<vector<int>>mod(len);
		for(int i=0;i<n;i++){
			if(dist[2*i] != 1e9){
				int x = dist[2*i];
				mod[x%len].push_back(x);	
			}
		}
		for(int i=0;i<len;i++)sort(mod[i].begin(),mod[i].end());
		for(int i=0;i<q;i++){
			int rem = G[i]%len;
			if(mod[rem].empty())continue;
			int pt = upper_bound(mod[rem].begin(),mod[rem].end(),G[i]) - mod[rem].begin();
			ans[i]+=pt;
		}
	}
	for(int i=0;i<q;i++)answer(ans[i]);
}

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