oj.uz

Submission #526427

# Submission time Handle Problem Language Result Execution time Memory
526427 2022-02-14T18:03:10 Z 1ne Regions (IOI09_regions) C++14
5 / 100
 2414 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<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.0 / 15.0

# Verdict Execution time Memory 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 Correct 9 ms 456 KB Output is correct
6 Incorrect 37 ms 2196 KB Output isn't correct
7 Incorrect 27 ms 840 KB Output isn't correct
8 Incorrect 42 ms 1864 KB Output isn't correct
9 Correct 809 ms 61928 KB Output is correct
10 Incorrect 137 ms 6084 KB Output isn't correct
11 Correct 378 ms 23208 KB Output is correct
12 Runtime error 598 ms 131076 KB Execution killed with signal 9
13 Incorrect 164 ms 4672 KB Output isn't correct
14 Correct 478 ms 25436 KB Output is correct
15 Runtime error 600 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 834 ms 131076 KB Execution killed with signal 9
2 Runtime error 792 ms 131076 KB Execution killed with signal 9
3 Runtime error 639 ms 131076 KB Execution killed with signal 9
4 Runtime error 849 ms 131076 KB Execution killed with signal 9
5 Runtime error 608 ms 131076 KB Execution killed with signal 9
6 Runtime error 846 ms 131076 KB Execution killed with signal 9
7 Runtime error 939 ms 131076 KB Execution killed with signal 9
8 Runtime error 678 ms 131076 KB Execution killed with signal 9
9 Runtime error 1851 ms 131076 KB Execution killed with signal 9
10 Runtime error 693 ms 131076 KB Execution killed with signal 9
11 Runtime error 1735 ms 131076 KB Execution killed with signal 9
12 Runtime error 2414 ms 131076 KB Execution killed with signal 9
13 Runtime error 1647 ms 131076 KB Execution killed with signal 9
14 Runtime error 2071 ms 131076 KB Execution killed with signal 9
15 Runtime error 853 ms 131076 KB Execution killed with signal 9
16 Runtime error 718 ms 131076 KB Execution killed with signal 9
17 Runtime error 666 ms 131076 KB Execution killed with signal 9