oj.uz

Submission #661131

# Submission time Handle Problem Language Result Execution time Memory
661131 2022-11-24T15:32:04 Z amirhoseinfar1385 Regions (IOI09_regions) C++17
100 / 100
 3432 ms 71716 KB 
#include<bits/stdc++.h>
using namespace std;
const int sq=(int)sqrt(200000+5),maxn=200000+5,maxr=25000+5,maxq=200000+5;
int now=0,valdfs[maxn],val[maxn],par[maxn],wr[maxr],allrsq[maxr][sq];
vector<int>allr[maxr],fallr[maxr];
pair<int,int>stf[maxn];
vector<int>adj[maxn];
vector<int>allbs;
int n,r,q,t=1;
 
bool cmp(int a,int b){
	return stf[a].first<stf[b].first;
}
 
void aval(int u=1){
	t++;
	stf[u].first=t;
	for(auto x:adj[u]){
		aval(x);
	}
	t++;
	stf[u].second=t;
}
 
void dovom(){
	for(int i=1;i<=r;i++){
		if(allr[i].size()>=sq){
			allbs.push_back(i);
			wr[i]=(int)allbs.size()-1;
		}
	}
}
 
void dfs(int u=1){
	valdfs[u]+=valdfs[par[u]];
	allrsq[val[u]][now]+=valdfs[u];
	for(auto x:adj[u]){
		dfs(x);
	}
}
 
void sevom(){
	for(int i=0;i<(int)allbs.size();i++){
		now=i;
		for(auto x:allr[allbs[i]]){
			valdfs[x]=1;
		}
		dfs();
		for(int i=0;i<maxn;i++){
			valdfs[i]=0;
		}
	}
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>r>>q;
	for(int i=1;i<=n;i++){
		if(i==1){
			int d;
			cin>>d;
			par[i]=0;
			val[i]=d;
			allr[d].push_back(i);
			continue;
		}
		int p,d;
		cin>>p>>d;
		par[i]=p;
		adj[p].push_back(i);
		val[i]=d;
		allr[d].push_back(i);
	}
	aval();
	dovom();
	sevom();
	for(int i=0;i<maxr;i++){
		sort(allr[i].begin(),allr[i].end(),cmp);
		for(auto x:allr[i]){
			fallr[i].push_back(stf[x].first);
		}
	}
	for(int asd=0;asd<q;asd++){
		int u,v;
		cin>>u>>v;
		if(allr[u].size()>=sq){
			cout<<allrsq[v][wr[u]]<<endl;
			continue;
		}
		else{
			int res=0;
			for(auto x:allr[u]){
				int ff=upper_bound(fallr[v].begin(),fallr[v].end(),stf[x].first)-fallr[v].begin();
				int fl=upper_bound(fallr[v].begin(),fallr[v].end(),stf[x].second)-fallr[v].begin();
				res+=fl-ff;
			}
			cout<<res<<endl;
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6096 KB Output is correct
2 Correct 4 ms 6096 KB Output is correct
3 Correct 6 ms 6224 KB Output is correct
4 Correct 7 ms 6224 KB Output is correct
5 Correct 11 ms 6224 KB Output is correct
6 Correct 18 ms 6212 KB Output is correct
7 Correct 28 ms 6224 KB Output is correct
8 Correct 32 ms 6224 KB Output is correct
9 Correct 43 ms 6736 KB Output is correct
10 Correct 71 ms 6736 KB Output is correct
11 Correct 103 ms 6992 KB Output is correct
12 Correct 131 ms 7504 KB Output is correct
13 Correct 86 ms 7248 KB Output is correct
14 Correct 228 ms 7844 KB Output is correct
15 Correct 251 ms 10468 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1433 ms 12332 KB Output is correct
2 Correct 1629 ms 11060 KB Output is correct
3 Correct 2296 ms 14128 KB Output is correct
4 Correct 275 ms 8016 KB Output is correct
5 Correct 324 ms 9608 KB Output is correct
6 Correct 602 ms 22120 KB Output is correct
7 Correct 1371 ms 28684 KB Output is correct
8 Correct 1133 ms 33788 KB Output is correct
9 Correct 1998 ms 16164 KB Output is correct
10 Correct 3250 ms 65736 KB Output is correct
11 Correct 3432 ms 16060 KB Output is correct
12 Correct 1159 ms 46080 KB Output is correct
13 Correct 1845 ms 46276 KB Output is correct
14 Correct 1973 ms 52916 KB Output is correct
15 Correct 2997 ms 66448 KB Output is correct
16 Correct 2655 ms 71716 KB Output is correct
17 Correct 2815 ms 61516 KB Output is correct