제출 #1286762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286762		liangjeremy	Regions (IOI09_regions)	C++20	100 / 100	3202 ms	32864 KiB

regions

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define fi first
#define se second
//#define int long long
using namespace std;
//using namespace __gnu_pbds;
using db=double;
using ll=int64_t;
using sll=__int128;
using lb=long double;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn=2e5+10; const int maxr=25010;
int n,r,q; vector<int>adj[maxn]; int a[maxn]; int f[maxr]; 
int timer=0; int in[maxn]; int out[maxn];
vector<int>h[maxr]; vector<int>v[maxr]; vector<vector<int>>tot; 
void euler(int node, int fa){
	timer++; in[node]=timer; v[a[node]].push_back(timer); 
	for(auto x:adj[node]){
		if(x!=fa)euler(x,node); 
	}
	out[node]=timer; 
}
void dfs(int node, int fa, int sum, int r1){
	tot[f[r1]][a[node]]+=sum; 
	for(auto x:adj[node]){
		if(x!=fa)dfs(x,node,sum+(a[node]==r1),r1);
	}
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(0));
    cin>>n>>r>>q; int block=sqrt(n); 
    for(int i=1; i<=n; i++){
    	if(i!=1){
    		int fa; cin>>fa; adj[i].push_back(fa); adj[fa].push_back(i); 
    	}
    	int s; cin>>s; h[s].push_back(i); a[i]=s; 
    }
    euler(1,0); int amt=-1; 
    for(int i=1; i<=r; i++){
    	if(h[i].size()>=block){
    		amt++; f[i]=amt; tot.push_back(vector<int>(r+1)); dfs(1,0,0,i); 
    	}
    }
    while(q--){
    	int r1,r2; cin>>r1>>r2; int ans=0; 
    	if(h[r1].size()<block){
    		for(auto x:h[r1]){
    			int end=upper_bound(v[r2].begin(),v[r2].end(),out[x])-v[r2].begin(); 
    			int st=lower_bound(v[r2].begin(),v[r2].end(),in[x])-v[r2].begin(); ans+=end-st; 
    		}
    		cout<<ans<<endl; 
    	}else cout<<tot[f[r1]][r2]<<endl; 
    }
}
/*
Overhead the albatross hangs motionless upon the air
And deep beneath the rolling waves in labyrinths of coral caves
The echo of a distant time comes willowing across the sand
And everything is green and submarine

And no one showed us to the land
And no one knows the wheres or whys
But something stirs and something tries
And starts to climb towards the light
*/

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85