oj.uz

Submission #526429

# Submission time Handle Problem Language Result Execution time Memory
526429 2022-02-14T18:06:57 Z 1ne Regions (IOI09_regions) C++14
5 / 100
 2345 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 3 ms 200 KB Output isn't correct
4 Incorrect 5 ms 200 KB Output isn't correct
5 Correct 9 ms 524 KB Output is correct
6 Incorrect 38 ms 2208 KB Output isn't correct
7 Incorrect 28 ms 840 KB Output isn't correct
8 Incorrect 48 ms 1968 KB Output isn't correct
9 Correct 798 ms 62004 KB Output is correct
10 Incorrect 147 ms 6272 KB Output isn't correct
11 Correct 406 ms 23232 KB Output is correct
12 Runtime error 671 ms 131076 KB Execution killed with signal 9
13 Incorrect 185 ms 4544 KB Output isn't correct
14 Correct 494 ms 25492 KB Output is correct
15 Runtime error 582 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 886 ms 131076 KB Execution killed with signal 9
2 Runtime error 752 ms 131076 KB Execution killed with signal 9
3 Runtime error 640 ms 131076 KB Execution killed with signal 9
4 Runtime error 830 ms 131076 KB Execution killed with signal 9
5 Runtime error 582 ms 131076 KB Execution killed with signal 9
6 Runtime error 822 ms 131076 KB Execution killed with signal 9
7 Runtime error 913 ms 131076 KB Execution killed with signal 9
8 Runtime error 621 ms 131076 KB Execution killed with signal 9
9 Runtime error 1782 ms 131076 KB Execution killed with signal 9
10 Runtime error 692 ms 131076 KB Execution killed with signal 9
11 Runtime error 1588 ms 131076 KB Execution killed with signal 9
12 Runtime error 2345 ms 131076 KB Execution killed with signal 9
13 Runtime error 1648 ms 131076 KB Execution killed with signal 9
14 Runtime error 2120 ms 131076 KB Execution killed with signal 9
15 Runtime error 870 ms 131076 KB Execution killed with signal 9
16 Runtime error 721 ms 131076 KB Execution killed with signal 9
17 Runtime error 659 ms 131076 KB Execution killed with signal 9