oj.uz

Submission #744660

# Submission time Handle Problem Language Result Execution time Memory
744660 2023-05-18T23:13:36 Z CSQ31 Tropical Garden (IOI11_garden) C++17
100 / 100
 135 ms 55020 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19284 KB Output is correct
2 Correct 11 ms 19232 KB Output is correct
3 Correct 11 ms 19292 KB Output is correct
4 Correct 11 ms 19048 KB Output is correct
5 Correct 11 ms 19160 KB Output is correct
6 Correct 12 ms 19328 KB Output is correct
7 Correct 11 ms 19104 KB Output is correct
8 Correct 11 ms 19156 KB Output is correct
9 Correct 13 ms 19472 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19284 KB Output is correct
2 Correct 11 ms 19232 KB Output is correct
3 Correct 11 ms 19292 KB Output is correct
4 Correct 11 ms 19048 KB Output is correct
5 Correct 11 ms 19160 KB Output is correct
6 Correct 12 ms 19328 KB Output is correct
7 Correct 11 ms 19104 KB Output is correct
8 Correct 11 ms 19156 KB Output is correct
9 Correct 13 ms 19472 KB Output is correct
10 Correct 10 ms 19160 KB Output is correct
11 Correct 22 ms 22052 KB Output is correct
12 Correct 32 ms 23968 KB Output is correct
13 Correct 71 ms 46800 KB Output is correct
14 Correct 111 ms 35188 KB Output is correct
15 Correct 135 ms 36220 KB Output is correct
16 Correct 97 ms 31964 KB Output is correct
17 Correct 93 ms 30296 KB Output is correct
18 Correct 38 ms 24240 KB Output is correct
19 Correct 98 ms 35164 KB Output is correct
20 Correct 120 ms 36152 KB Output is correct
21 Correct 109 ms 32168 KB Output is correct
22 Correct 89 ms 30120 KB Output is correct
23 Correct 130 ms 36944 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19284 KB Output is correct
2 Correct 11 ms 19232 KB Output is correct
3 Correct 11 ms 19292 KB Output is correct
4 Correct 11 ms 19048 KB Output is correct
5 Correct 11 ms 19160 KB Output is correct
6 Correct 12 ms 19328 KB Output is correct
7 Correct 11 ms 19104 KB Output is correct
8 Correct 11 ms 19156 KB Output is correct
9 Correct 13 ms 19472 KB Output is correct
10 Correct 10 ms 19160 KB Output is correct
11 Correct 22 ms 22052 KB Output is correct
12 Correct 32 ms 23968 KB Output is correct
13 Correct 71 ms 46800 KB Output is correct
14 Correct 111 ms 35188 KB Output is correct
15 Correct 135 ms 36220 KB Output is correct
16 Correct 97 ms 31964 KB Output is correct
17 Correct 93 ms 30296 KB Output is correct
18 Correct 38 ms 24240 KB Output is correct
19 Correct 98 ms 35164 KB Output is correct
20 Correct 120 ms 36152 KB Output is correct
21 Correct 109 ms 32168 KB Output is correct
22 Correct 89 ms 30120 KB Output is correct
23 Correct 130 ms 36944 KB Output is correct
24 Correct 11 ms 19156 KB Output is correct
25 Correct 20 ms 22088 KB Output is correct
26 Correct 35 ms 24060 KB Output is correct
27 Correct 68 ms 46816 KB Output is correct
28 Correct 118 ms 35272 KB Output is correct
29 Correct 132 ms 36220 KB Output is correct
30 Correct 92 ms 31952 KB Output is correct
31 Correct 103 ms 30268 KB Output is correct
32 Correct 36 ms 24128 KB Output is correct
33 Correct 94 ms 35264 KB Output is correct
34 Correct 125 ms 36224 KB Output is correct
35 Correct 111 ms 32028 KB Output is correct
36 Correct 85 ms 30344 KB Output is correct
37 Correct 102 ms 36872 KB Output is correct
38 Correct 111 ms 55020 KB Output is correct