oj.uz

답안 #526428

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526428 2022-02-14T18:05:55 Z 1ne Regions (IOI09_regions) C++14
1 / 100
 2590 ms 131076 KB 
#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<bool>op(n,false);
op[region[0]]=true;
vector<vector<int>>arr(r);

for (int i = 1;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;
			if (x==0){
				op[region[0]]=true;
				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 (op[x]){
		cout<<region_count[y]<<endl;
		continue;
	}
	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
1.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Incorrect 1 ms 200 KB Output isn't correct
3 Incorrect 1 ms 200 KB Output isn't correct
4 Incorrect 5 ms 200 KB Output isn't correct
5 Incorrect 10 ms 512 KB Output isn't correct
6 Incorrect 38 ms 2204 KB Output isn't correct
7 Incorrect 34 ms 840 KB Output isn't correct
8 Incorrect 48 ms 1864 KB Output isn't correct
9 Incorrect 840 ms 62044 KB Output isn't correct
10 Incorrect 170 ms 6236 KB Output isn't correct
11 Incorrect 401 ms 23684 KB Output isn't correct
12 Runtime error 671 ms 131076 KB Execution killed with signal 9
13 Incorrect 116 ms 4568 KB Output isn't correct
14 Incorrect 512 ms 25316 KB Output isn't correct
15 Runtime error 609 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 844 ms 131076 KB Execution killed with signal 9
2 Runtime error 826 ms 131076 KB Execution killed with signal 9
3 Runtime error 674 ms 131076 KB Execution killed with signal 9
4 Runtime error 867 ms 131076 KB Execution killed with signal 9
5 Runtime error 666 ms 131076 KB Execution killed with signal 9
6 Runtime error 876 ms 131076 KB Execution killed with signal 9
7 Runtime error 992 ms 131076 KB Execution killed with signal 9
8 Runtime error 665 ms 131076 KB Execution killed with signal 9
9 Runtime error 1964 ms 131076 KB Execution killed with signal 9
10 Runtime error 721 ms 131076 KB Execution killed with signal 9
11 Runtime error 1689 ms 131076 KB Execution killed with signal 9
12 Runtime error 2590 ms 131076 KB Execution killed with signal 9
13 Runtime error 1627 ms 131076 KB Execution killed with signal 9
14 Runtime error 2216 ms 131076 KB Execution killed with signal 9
15 Runtime error 887 ms 131076 KB Execution killed with signal 9
16 Runtime error 731 ms 131076 KB Execution killed with signal 9
17 Runtime error 691 ms 131076 KB Execution killed with signal 9