oj.uz

Submission #416121

# Submission time Handle Problem Language Result Execution time Memory
416121 2021-06-02T02:32:28 Z dreezy Tropical Garden (IOI11_garden) C++17
100 / 100
 3135 ms 44736 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 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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 18380 KB Output is correct
2 Correct 17 ms 18260 KB Output is correct
3 Correct 15 ms 18252 KB Output is correct
4 Correct 14 ms 18172 KB Output is correct
5 Correct 16 ms 18108 KB Output is correct
6 Correct 16 ms 18380 KB Output is correct
7 Correct 15 ms 18124 KB Output is correct
8 Correct 16 ms 18344 KB Output is correct
9 Correct 18 ms 18296 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 18380 KB Output is correct
2 Correct 17 ms 18260 KB Output is correct
3 Correct 15 ms 18252 KB Output is correct
4 Correct 14 ms 18172 KB Output is correct
5 Correct 16 ms 18108 KB Output is correct
6 Correct 16 ms 18380 KB Output is correct
7 Correct 15 ms 18124 KB Output is correct
8 Correct 16 ms 18344 KB Output is correct
9 Correct 18 ms 18296 KB Output is correct
10 Correct 14 ms 18124 KB Output is correct
11 Correct 24 ms 20536 KB Output is correct
12 Correct 45 ms 22084 KB Output is correct
13 Correct 81 ms 37492 KB Output is correct
14 Correct 184 ms 33556 KB Output is correct
15 Correct 192 ms 33916 KB Output is correct
16 Correct 201 ms 29492 KB Output is correct
17 Correct 146 ms 27992 KB Output is correct
18 Correct 52 ms 22704 KB Output is correct
19 Correct 157 ms 33592 KB Output is correct
20 Correct 199 ms 33988 KB Output is correct
21 Correct 157 ms 29452 KB Output is correct
22 Correct 184 ms 28012 KB Output is correct
23 Correct 189 ms 35232 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 18380 KB Output is correct
2 Correct 17 ms 18260 KB Output is correct
3 Correct 15 ms 18252 KB Output is correct
4 Correct 14 ms 18172 KB Output is correct
5 Correct 16 ms 18108 KB Output is correct
6 Correct 16 ms 18380 KB Output is correct
7 Correct 15 ms 18124 KB Output is correct
8 Correct 16 ms 18344 KB Output is correct
9 Correct 18 ms 18296 KB Output is correct
10 Correct 14 ms 18124 KB Output is correct
11 Correct 24 ms 20536 KB Output is correct
12 Correct 45 ms 22084 KB Output is correct
13 Correct 81 ms 37492 KB Output is correct
14 Correct 184 ms 33556 KB Output is correct
15 Correct 192 ms 33916 KB Output is correct
16 Correct 201 ms 29492 KB Output is correct
17 Correct 146 ms 27992 KB Output is correct
18 Correct 52 ms 22704 KB Output is correct
19 Correct 157 ms 33592 KB Output is correct
20 Correct 199 ms 33988 KB Output is correct
21 Correct 157 ms 29452 KB Output is correct
22 Correct 184 ms 28012 KB Output is correct
23 Correct 189 ms 35232 KB Output is correct
24 Correct 16 ms 18252 KB Output is correct
25 Correct 124 ms 20932 KB Output is correct
26 Correct 184 ms 22732 KB Output is correct
27 Correct 2748 ms 38544 KB Output is correct
28 Correct 1115 ms 33700 KB Output is correct
29 Correct 3024 ms 33968 KB Output is correct
30 Correct 1779 ms 29632 KB Output is correct
31 Correct 1676 ms 28028 KB Output is correct
32 Correct 155 ms 22724 KB Output is correct
33 Correct 1120 ms 33704 KB Output is correct
34 Correct 3135 ms 33960 KB Output is correct
35 Correct 1979 ms 29504 KB Output is correct
36 Correct 1739 ms 28028 KB Output is correct
37 Correct 933 ms 35348 KB Output is correct
38 Correct 2498 ms 44736 KB Output is correct