oj.uz

Submission #416096

# Submission time Handle Problem Language Result Execution time Memory
416096 2021-06-02T00:44:45 Z dreezy Tropical Garden (IOI11_garden) C++17
0 / 100
 23 ms 36700 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 36660 KB Output is correct
2 Correct 21 ms 36632 KB Output is correct
3 Correct 18 ms 36700 KB Output is correct
4 Correct 23 ms 36692 KB Output is correct
5 Incorrect 23 ms 36688 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 36660 KB Output is correct
2 Correct 21 ms 36632 KB Output is correct
3 Correct 18 ms 36700 KB Output is correct
4 Correct 23 ms 36692 KB Output is correct
5 Incorrect 23 ms 36688 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 36660 KB Output is correct
2 Correct 21 ms 36632 KB Output is correct
3 Correct 18 ms 36700 KB Output is correct
4 Correct 23 ms 36692 KB Output is correct
5 Incorrect 23 ms 36688 KB Output isn't correct
6 Halted 0 ms 0 KB -