Submission #526432

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526432	2022-02-14T18:20:04 Z	1ne	Regions (IOI09_regions)	C++14	13 / 100	1567 ms	131076 KB

regions

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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