oj.uz

답안 #526433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526433 2022-02-14T18:32:35 Z 1ne Regions (IOI09_regions) C++14
13 / 100
 1113 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);
for (int64_t i = 1;i<n;++i){
	cin>>parent[i]>>region[i];
	parent[i]--;
	adj[parent[i]].push_back(i);
	region[i]--;
}
 
vector<vector<int64_t>>arr(r);
vector<bool>visited(n,false);
for (int64_t i = 0;i<n;++i){
	if (visited[i]){
		continue;
	}
	vector<int64_t>region_count(r,0);
	function<void(int64_t)> dfs = [&](int64_t cur){
		if (visited[cur]){
			return;
		}
		visited[cur]=true;
		for (int j = 0;j<r;++j){
			for (int k = 0;k<region_count[j];++k){
				arr[j].push_back(region[cur]);
			}
		}
		region_count[region[cur]]++;
		for (auto x:adj[cur]){
			dfs(x);
		}
		region_count[region[cur]]--;
	};
	dfs(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 (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){
			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 2 ms 200 KB Output is correct
4 Correct 5 ms 328 KB Output is correct
5 Correct 9 ms 712 KB Output is correct
6 Correct 22 ms 4116 KB Output is correct
7 Correct 46 ms 1432 KB Output is correct
8 Correct 51 ms 3528 KB Output is correct
9 Correct 459 ms 124560 KB Output is correct
10 Correct 143 ms 12580 KB Output is correct
11 Correct 324 ms 46700 KB Output is correct
12 Runtime error 172 ms 131076 KB Execution killed with signal 9
13 Correct 227 ms 7988 KB Output is correct
14 Correct 383 ms 52636 KB Output is correct
15 Runtime error 179 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 159 ms 131076 KB Execution killed with signal 9
2 Runtime error 164 ms 131076 KB Execution killed with signal 9
3 Runtime error 169 ms 131076 KB Execution killed with signal 9
4 Runtime error 296 ms 131076 KB Execution killed with signal 9
5 Runtime error 258 ms 131076 KB Execution killed with signal 9
6 Runtime error 381 ms 131072 KB Execution killed with signal 9
7 Runtime error 462 ms 131076 KB Execution killed with signal 9
8 Runtime error 354 ms 131076 KB Execution killed with signal 9
9 Runtime error 466 ms 131076 KB Execution killed with signal 9
10 Runtime error 493 ms 131076 KB Execution killed with signal 9
11 Runtime error 1113 ms 131076 KB Execution killed with signal 9
12 Runtime error 692 ms 131076 KB Execution killed with signal 9
13 Runtime error 623 ms 131076 KB Execution killed with signal 9
14 Runtime error 821 ms 131076 KB Execution killed with signal 9
15 Runtime error 527 ms 131076 KB Execution killed with signal 9
16 Runtime error 507 ms 131076 KB Execution killed with signal 9
17 Runtime error 484 ms 131076 KB Execution killed with signal 9