oj.uz

Submission #661130

# Submission time Handle Problem Language Result Execution time Memory
661130 2022-11-24T15:27:06 Z amirhoseinfar1385 Regions (IOI09_regions) C++17
35 / 100
 3426 ms 71728 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]++;
	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[wr[u]][v]<<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 3 ms 6104 KB Output is correct
3 Correct 4 ms 6096 KB Output is correct
4 Correct 8 ms 6224 KB Output is correct
5 Correct 10 ms 6224 KB Output is correct
6 Correct 22 ms 6224 KB Output is correct
7 Correct 22 ms 6224 KB Output is correct
8 Correct 31 ms 6224 KB Output is correct
9 Correct 45 ms 6736 KB Output is correct
10 Correct 86 ms 6792 KB Output is correct
11 Correct 112 ms 7020 KB Output is correct
12 Correct 129 ms 7504 KB Output is correct
13 Correct 164 ms 7248 KB Output is correct
14 Correct 185 ms 7860 KB Output is correct
15 Correct 259 ms 10448 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1445 ms 12244 KB Output isn't correct
2 Incorrect 1858 ms 11100 KB Output isn't correct
3 Incorrect 2457 ms 14156 KB Output isn't correct
4 Correct 211 ms 7924 KB Output is correct
5 Correct 227 ms 9552 KB Output is correct
6 Incorrect 571 ms 22124 KB Output isn't correct
7 Incorrect 1231 ms 28684 KB Output isn't correct
8 Incorrect 1117 ms 33932 KB Output isn't correct
9 Correct 2110 ms 16120 KB Output is correct
10 Incorrect 3234 ms 65740 KB Output isn't correct
11 Correct 3426 ms 16072 KB Output is correct
12 Incorrect 1096 ms 46024 KB Output isn't correct
13 Incorrect 1733 ms 46184 KB Output isn't correct
14 Incorrect 2182 ms 52904 KB Output isn't correct
15 Incorrect 2980 ms 66448 KB Output isn't correct
16 Incorrect 3022 ms 71728 KB Output isn't correct
17 Incorrect 2868 ms 61436 KB Output isn't correct