Submission #416121

#	Time	Username	Problem	Language	Result	Execution time	Memory
416121		dreezy	Tropical Garden (IOI11_garden)	C++17	100 / 100	3135 ms	44736 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;


/*****************************************/

//just have to implement
#define pi pair<int,int>
#define pb insert
#define ll long long
#define f first
#define s second

const int maxn = 3e5 + 5;
const int logn = 1;
//int level[maxn];
set<int> rgraph[maxn];
bool vis[maxn];
int up[maxn][logn];
int distroot[maxn][2];

int cycle[2];

void dfs(int root, int node, int dist){
	vis[node] = true;
	distroot[node][root%2] = dist;
	
	for(int adj : rgraph[node]){
		if(adj == root){
			cycle[root%2] = dist +1;
			//cout << "cycle: "<<node<<endl;
		}
		
		if(vis[adj]) continue;
		
		dfs(root, adj, dist + 1);
	}
}


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 a = 2* R[i][0];
		int b = 2* R[i][1];
		
		if(up[a][0] == -1){
			if( up[b][0] == -1){
				up[a][0] = b+1;
				up[a+1][0] = b+1;	
				
				rgraph[b+1].pb(a);
				rgraph[b+1].pb(a+1);
			}
			else{
				up[a][0] = b;
				up[a+1][0] = b;	
				rgraph[b].pb(a);
				rgraph[b].pb(a+1);
			}
		}
		else if(up[a][0] == up[a+1][0]){
			rgraph[up[a+1][0]].erase(a+1);
			if(up[b][0] == -1)
				{
					
					up[a+1][0] = b+1;
					rgraph[b+1].pb(a+1);
				}
			else
				{
					up[a+1][0] = b;
					rgraph[b].pb(a+1);
				}
		}
		
		if(up[b][0] == -1){
			
			if(up[a][0] == b +1){
				up[b][0] = a+1;
				up[b+1][0] = a+1;
				rgraph[a+1].pb(b);
				rgraph[a+1].pb(b+1);
				
			}
			else{	
				up[b][0] = a;
				up[b+1][0]= a;
				rgraph[a].pb(b);
				rgraph[a].pb(b+1);
			}
		}
		else if(up[b][0] == up[b+1][0]){
			rgraph[up[b+1][0]].erase(b+1);
			if(up[a][0] == b)
				{
					up[b+1][0] = a+1;
					rgraph[a+1].pb(b+1);
				}
			else
				{
					up[b+1][0] = a;
					rgraph[a].pb(b+1);
				}
		}
	}
	
	
	
	/*for(int i =0; i< N; i++){
		int a = up[i*2][0];
		int b= up[i*2 +1][0];
		
		if(a % 2== 1){
			cout << i  <<" -> "<<a/2<<"'\n";
		}
		else{
			cout << i  <<" -> "<<a/2<<"\n";
		}
		
		if(b % 2== 1){
			cout << i  <<"' -> "<<b/2<<"'\n";
		}
		else{
			cout << i  <<"' -> "<<b/2<<"\n";
		}
	}*/
	
	/*
	for(int i =1;i<=5; i++){
		int res = jump(0, i);
		if(res % 2 == 1)
			cout << "0 + "<<i<<"  -> "<<res/2<<"'\n";
		else
			cout << "0 + "<<i<<"  -> "<<res/2<<"\n";
	
	}
	
	*/
	
	/*
	for(int i =0; i<N; i++){
		cout << i <<": ";
		
		for(int adj : rgraph[2*i])
			cout << adj <<", ";
		cout <<endl;
		
		cout << i<<"': ";
		
		for(int adj : rgraph[2*i +1])
			cout <<adj<<", ";
		cout <<endl;
	}*/
	
	for(int i =0; i< maxn; i++ )
		distroot[i][0] = distroot[i][1] = -1;
		
	
	cycle[0] = cycle[1] = -1;
	
	
	dfs(2*P, 2*P, 0);
	memset(vis, 0, sizeof vis);
	dfs(2*P+1, 2*P +1, 0);
	
/*cout << cycle[0]<<", "<<cycle[1]<<":\n";
	for(int i=0; i<N; i++){
		cout <<i<<": "<< distroot[i*2][0]<<", "<<distroot[i*2][1]<<endl;
		
	}
	*/
	for(int i =0; i<Q; i++){
		ll ans = 0;
		//G[i] = 100 - i;
		
		for(int j =0; j<N; j++){
			if(distroot[j *2][0] != -1){
				if(distroot[j*2][0] == G[i])
				{
					ans++;
					continue;
				}
				else if(cycle[0]!= -1 && G[i] > distroot[j*2][0]){
					if( (G[i] - distroot[j*2][0]) % cycle[0] == 0){
						ans++;
						continue;
					}
				}
			}
			if(distroot[j*2][1] != -1){
				if(distroot[j*2 ][1] == G[i])
					ans++;
				else if(cycle[1] != -1 && G[i] > distroot[j*2][1])
					if( (G[i] - distroot[j*2][1]) % cycle[1] == 0)
						ans++;
			}
		}
		answer(ans);  
	}

   
}
/******************************************/

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