oj.uz

Submission #661183

# Submission time Handle Problem Language Result Execution time Memory
661183 2022-11-24T20:57:57 Z amirhoseinfar1385 Regions (IOI09_regions) C++14
100 / 100
 3098 ms 71752 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 4 ms 6096 KB Output is correct
2 Correct 4 ms 6096 KB Output is correct
3 Correct 5 ms 6096 KB Output is correct
4 Correct 7 ms 6224 KB Output is correct
5 Correct 11 ms 6224 KB Output is correct
6 Correct 23 ms 6224 KB Output is correct
7 Correct 24 ms 6224 KB Output is correct
8 Correct 50 ms 6352 KB Output is correct
9 Correct 72 ms 6736 KB Output is correct
10 Correct 112 ms 6736 KB Output is correct
11 Correct 122 ms 6992 KB Output is correct
12 Correct 118 ms 7504 KB Output is correct
13 Correct 150 ms 7248 KB Output is correct
14 Correct 180 ms 7888 KB Output is correct
15 Correct 243 ms 10448 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1364 ms 12236 KB Output is correct
2 Correct 1851 ms 11076 KB Output is correct
3 Correct 2251 ms 14156 KB Output is correct
4 Correct 262 ms 7932 KB Output is correct
5 Correct 349 ms 9552 KB Output is correct
6 Correct 634 ms 22248 KB Output is correct
7 Correct 1279 ms 28608 KB Output is correct
8 Correct 1136 ms 33760 KB Output is correct
9 Correct 1736 ms 16072 KB Output is correct
10 Correct 3067 ms 65740 KB Output is correct
11 Correct 3098 ms 16040 KB Output is correct
12 Correct 1289 ms 46072 KB Output is correct
13 Correct 1606 ms 46280 KB Output is correct
14 Correct 2116 ms 52900 KB Output is correct
15 Correct 2646 ms 66444 KB Output is correct
16 Correct 2992 ms 71752 KB Output is correct
17 Correct 2707 ms 61456 KB Output is correct