Submission #416096

#	Time	Username	Problem	Language	Result	Execution time	Memory
416096		dreezy	Tropical Garden (IOI11_garden)	C++17	0 / 100	23 ms	36700 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 push_back
#define ll long long
#define f first
#define s second

const int maxn = 3e5 + 5;
const int logn = 31;
//int level[maxn];
int up[maxn][logn];


int jump(int n, int k){
	
	for(int lvl = 0; lvl< logn; lvl++){
		if( ( 1<< lvl) & k)
			n = up[n][lvl];
	}
	
	return n;
	
}





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;	
				
			}
			else{
				up[a][0] = b;
				up[a+1][0] = b;	
			}
		}
		else if(up[a][0] == up[a+1][0]){
			if(up[b][0] == -1)
				up[a+1][0] = b+1;
		}
		
		if(up[b][0] == -1){
			
			if(up[a][0] == b +1){
				up[b][0] = a+1;
				up[b+1][0] = a+1;
				
			}
			else{	
				up[b][0] = a;
				up[b+1][0]= a;
			}
		}
		else if(up[b][0] == up[b+1][0]){
			if(up[a][0] == b)
				up[b+1][0] = a+1;
				
			up[b+1][0] = a;
		}
	}
	
	
	for(int lvl = 1; lvl< logn; lvl++){
		for(int i = 0; i<2*N; i++){
			up[i][lvl] = up[up[i][lvl-1]][lvl-1];
		}
	}
	
	/*
	for(int i =0; i< N; i++){
		int a = graph[i*2];
		int b= graph[i*2 +1];
		
		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 =0; i<Q; i++){
		ll ans = 0;
		
		for(int j =0; j<N; j++){
			ans+=(jump(j*2,G[i]) /2) == P;
		}
		answer(ans);  
	}

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

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