Submission #526428

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526428	2022-02-14T18:05:55 Z	1ne	Regions (IOI09_regions)	C++14	1 / 100	2590 ms	131076 KB

regions

#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

#	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	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

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