제출 #526429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
526429		1ne	Regions (IOI09_regions)	C++14	5 / 100	2345 ms	131076 KiB

regions

#include<bits/stdc++.h>
using namespace std;
 
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,r,q;cin>>n>>r>>q;
vector<int>region(n,-1),parent(n,-1);
cin>>region[0];
region[0]--;
vector<vector<int>>adj(n);
vector<int>region_count(r,0);
for (int i = 1;i<n;++i){
	//adj[0].push_back(i);
	cin>>parent[i]>>region[i];
	parent[i]--;
	adj[parent[i]].push_back(i);
	region[i]--;
	region_count[region[i]]++;
}
 
vector<vector<int>>arr(r);
 
for (int i = 0;i<n;++i){
	vector<bool>visited(n,false);
	function<void(int , int)> dfs = [&](int cur,int par){
		visited[cur] = true;
		for (auto x:adj[cur]){
			if (visited[x])continue;
			arr[region[par]].push_back(region[x]);
			dfs(x,par);
		}
	};
	dfs(i,i);
}
for (int i = 0;i<r;++i){
	sort(arr[i].begin(),arr[i].end());
}
for (int i = 0;i<q;++i){
	int x,y;cin>>x>>y;
	--x;
	--y;
	if (arr[x].empty()){
		cout<<0<<endl;
		continue;
	}
	int ans = 0;
	int left = 0,right = arr[x].size()-1;
	while(left<=right){
		int mid = (left + right)>>1;
		if (arr[x][mid]<=y){
			left = mid + 1;
			ans = max(ans,mid);
		}
		else{
			right = mid - 1;
		}
	}
	int ans2 = INT_MAX;
	int left2 = 0,right2 = arr[x].size()-1;
	while(left2<=right2){
		int mid = (left2 + right2)>>1;
		if (arr[x][mid]>=y){
			ans2 = min(ans2,mid);
			right2 = mid - 1;
		}
		else left2 = mid + 1;
	}
	cout<<max(ans - ans2 + 1,0)<<endl;
	
}
return 0;}

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