oj.uz

답안 #526432

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526432 2022-02-14T18:20:04 Z 1ne Regions (IOI09_regions) C++14
13 / 100
 1567 ms 131076 KB 
#include<bits/stdc++.h>
using namespace std;
 
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int64_t n,r,q;cin>>n>>r>>q;
vector<int64_t>region(n,-1),parent(n,-1);
cin>>region[0];
region[0]--;
vector<vector<int64_t>>adj(n);
vector<int64_t>region_count(r,0);
for (int64_t 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<int64_t>>arr(r);
 
for (int64_t i = 0;i<n;++i){
	vector<bool>visited(n,false);
	function<void(int64_t , int64_t)> dfs = [&](int64_t cur,int64_t par){
		visited[cur]=true;
		for (auto x:adj[cur]){
			if (visited[x])continue;
			visited[x]=true;
			arr[region[par]].push_back(region[x]);
			dfs(x,par);
		}
	};
	dfs(i,i);
}
for (int64_t i = 0;i<r;++i){
	sort(arr[i].begin(),arr[i].end());
}
for (int64_t i = 0;i<q;++i){
	int64_t x,y;cin>>x>>y;
	--x;
	--y;
	//if (x==region[0]){
//		cout<<region_count[y]<<endl;
	//	continue;//
	//}
	if (arr[x].empty()){
		cout<<0<<endl;
		continue;
	}
	int64_t ans = 0;
	int64_t left = 0,right = arr[x].size()-1;
	while(left<=right){
		int64_t mid = (left + right)>>1;
		if (arr[x][mid]<=y){
			left = mid + 1;
		}
		else{
			right = mid - 1;
		}
		if (arr[x][mid]==y){
			ans = max(ans,mid);
		}
	}
	int64_t ans2 = INT_MAX;
	int64_t left2 = 0,right2 = arr[x].size()-1;
	while(left2<=right2){
		int64_t mid = (left2 + right2)>>1;
		if (arr[x][mid]>=y){
			//ans2 = min(ans2,mid);
			right2 = mid - 1;
		}
		else left2 = mid + 1;
		if (arr[x][mid]==y){
			ans2 = min(ans2,mid);
		}
	}
	cout<<max(ans - ans2 + 1,(int64_t)0)<<endl;
	
}
return 0;}

Subtask #1
13.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 3 ms 200 KB Output is correct
4 Correct 5 ms 328 KB Output is correct
5 Correct 9 ms 684 KB Output is correct
6 Correct 42 ms 3756 KB Output is correct
7 Correct 38 ms 1360 KB Output is correct
8 Correct 57 ms 3264 KB Output is correct
9 Correct 963 ms 121668 KB Output is correct
10 Correct 175 ms 10672 KB Output is correct
11 Correct 494 ms 44288 KB Output is correct
12 Runtime error 509 ms 131076 KB Execution killed with signal 9
13 Correct 199 ms 7896 KB Output is correct
14 Correct 596 ms 48560 KB Output is correct
15 Runtime error 471 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 635 ms 131076 KB Execution killed with signal 9
2 Runtime error 601 ms 131076 KB Execution killed with signal 9
3 Runtime error 522 ms 131076 KB Execution killed with signal 9
4 Runtime error 703 ms 131076 KB Execution killed with signal 9
5 Runtime error 484 ms 131076 KB Execution killed with signal 9
6 Runtime error 673 ms 131076 KB Execution killed with signal 9
7 Runtime error 778 ms 131076 KB Execution killed with signal 9
8 Runtime error 447 ms 131076 KB Execution killed with signal 9
9 Runtime error 1279 ms 131076 KB Execution killed with signal 9
10 Runtime error 562 ms 131076 KB Execution killed with signal 9
11 Runtime error 1116 ms 131076 KB Execution killed with signal 9
12 Runtime error 1567 ms 131076 KB Execution killed with signal 9
13 Runtime error 1071 ms 131076 KB Execution killed with signal 9
14 Runtime error 1447 ms 131076 KB Execution killed with signal 9
15 Runtime error 621 ms 131076 KB Execution killed with signal 9
16 Runtime error 509 ms 131076 KB Execution killed with signal 9
17 Runtime error 459 ms 131076 KB Execution killed with signal 9