제출 #1175793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175793		mertbbm	Regions (IOI09_regions)	C++20	100 / 100	3279 ms	41912 KiB

regions

#include <bits/stdc++.h>
using namespace std;

//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

const int blk=500;
vector<int>adj[200005];
int in[200005];
int out[200005];
int arr[200005];
int ptr=0;
vector<int>order;

void dfs(int index, int par){
	in[index]=++ptr;
	order.push_back(index);
	for(auto it:adj[index]){
		if(it==par) continue;
		dfs(it,index);
	}
	out[index]=ptr;
}

int val[605][200005];

void dfs2(int index, int color, int cur, int ptr, int par){
	if(arr[index]==color) cur++;
	else val[ptr][arr[index]]+=cur;
	for(auto it:adj[index]){
		if(it==par) continue;
		dfs2(it,color,cur,ptr,index);
	}
}

vector<int>storage[200005];
vector<int>st[200005];

void solve(){
	int n,m,q;
	cin >> n >> m >> q;

	int cnt[m+5];
	memset(cnt,0,sizeof(cnt));
	int temp,temp2;
	cin >> arr[1];
	cnt[arr[1]]++;
	storage[arr[1]].push_back(1);
	for(int x=2;x<=n;x++){
		cin >> temp >> temp2;
		arr[x]=temp2;
		adj[x].push_back(temp);
		adj[temp].push_back(x);
		cnt[arr[x]]++;
		storage[arr[x]].push_back(x);
	}
	
	order.push_back(0);
	dfs(1,-1);
	
	int hash[m+5];
	int counter=0;
	for(int x=1;x<=m;x++){
		if(cnt[x]>blk){
			dfs2(1,x,0,counter,-1);
			hash[x]=counter++;
		}
	}
	
	for(int x=1;x<=n;x++){
		st[arr[x]].push_back(in[x]);
	}
	
	for(int x=1;x<=m;x++){
		sort(st[x].begin(),st[x].end());
	}
	
	for(int x=0;x<q;x++){
		cin >> temp >> temp2;
		if(cnt[temp]>blk){
			int ans=val[hash[temp]][temp2];
			cout << ans << endl;
		}
		else{
			int ans=0;
			for(auto it:storage[temp]){
				int l=lower_bound(st[temp2].begin(),st[temp2].end(),in[it])-st[temp2].begin();
				int r=upper_bound(st[temp2].begin(),st[temp2].end(),out[it])-st[temp2].begin();
				ans+=r-l;
			}
			cout << ans << endl;
		}
	}
}
																   
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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