답안 #661130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
661130	2022-11-24T15:27:06 Z	amirhoseinfar1385	Regions (IOI09_regions)	C++17	35 / 100	3426 ms	71728 KB

regions

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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