oj.uz

Submission #661128

# Submission time Handle Problem Language Result Execution time Memory
661128 2022-11-24T15:24:36 Z amirhoseinfar1385 Regions (IOI09_regions) C++17
0 / 100
 467 ms 71772 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]<<"\n";
			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<<"\n";
		}
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 6096 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 6096 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 6096 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 6224 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 6224 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 6224 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 6224 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 6736 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 6736 KB Time limit exceeded (wall clock)
11 Execution timed out 7 ms 6992 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 7504 KB Time limit exceeded (wall clock)
13 Execution timed out 10 ms 7300 KB Time limit exceeded (wall clock)
14 Execution timed out 12 ms 7816 KB Time limit exceeded (wall clock)
15 Execution timed out 20 ms 10568 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 71 ms 12212 KB Time limit exceeded (wall clock)
2 Execution timed out 52 ms 10992 KB Time limit exceeded (wall clock)
3 Execution timed out 43 ms 14152 KB Time limit exceeded (wall clock)
4 Execution timed out 15 ms 7924 KB Time limit exceeded (wall clock)
5 Execution timed out 13 ms 9552 KB Time limit exceeded (wall clock)
6 Execution timed out 127 ms 22192 KB Time limit exceeded (wall clock)
7 Execution timed out 87 ms 28616 KB Time limit exceeded (wall clock)
8 Execution timed out 227 ms 33728 KB Time limit exceeded (wall clock)
9 Execution timed out 55 ms 16144 KB Time limit exceeded (wall clock)
10 Execution timed out 346 ms 65752 KB Time limit exceeded (wall clock)
11 Execution timed out 81 ms 16072 KB Time limit exceeded (wall clock)
12 Execution timed out 126 ms 46024 KB Time limit exceeded (wall clock)
13 Execution timed out 112 ms 46316 KB Time limit exceeded (wall clock)
14 Execution timed out 467 ms 52808 KB Time limit exceeded (wall clock)
15 Execution timed out 105 ms 66424 KB Time limit exceeded (wall clock)
16 Execution timed out 97 ms 71772 KB Time limit exceeded (wall clock)
17 Execution timed out 185 ms 61464 KB Time limit exceeded (wall clock)