Submission #526304

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526304	2022-02-14T08:49:19 Z	1ne	Regions (IOI09_regions)	C++14	0 / 100	2043 ms	33608 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>visited(n,false);
vector<vector<int>>arr(r);
function<void(int , int)> dfs = [&](int cur,int par){
	visited[cur] = true;
	for (auto x:adj[cur]){
		if (x==par)continue;
		arr[region[cur]].push_back(region[x]);
		dfs(x,cur);
	}
};
for (int i = 1;i<n;++i){
	if (!visited[i])
		dfs(i,-1);
}
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 (x==region[0]){
		cout<<region_count[y]<<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<<ans - ans2 + 1<<endl;
	
}
return 0;}

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	200 KB	Output isn't correct
2	Incorrect	1 ms	200 KB	Output isn't correct
3	Incorrect	2 ms	200 KB	Output isn't correct
4	Incorrect	4 ms	200 KB	Output isn't correct
5	Incorrect	7 ms	328 KB	Output isn't correct
6	Incorrect	17 ms	328 KB	Output isn't correct
7	Incorrect	29 ms	328 KB	Output isn't correct
8	Incorrect	33 ms	456 KB	Output isn't correct
9	Incorrect	35 ms	1096 KB	Output isn't correct
10	Incorrect	82 ms	968 KB	Output isn't correct
11	Incorrect	96 ms	1480 KB	Output isn't correct
12	Incorrect	98 ms	2248 KB	Output isn't correct
13	Incorrect	109 ms	1736 KB	Output isn't correct
14	Incorrect	133 ms	2452 KB	Output isn't correct
15	Incorrect	133 ms	6980 KB	Output isn't correct

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	435 ms	7016 KB	Output isn't correct
2	Incorrect	726 ms	5332 KB	Output isn't correct
3	Incorrect	1210 ms	10016 KB	Output isn't correct
4	Incorrect	178 ms	2644 KB	Output isn't correct
5	Incorrect	305 ms	5556 KB	Output isn't correct
6	Incorrect	562 ms	4580 KB	Output isn't correct
7	Incorrect	633 ms	5824 KB	Output isn't correct
8	Incorrect	933 ms	14256 KB	Output isn't correct
9	Incorrect	1340 ms	13364 KB	Output isn't correct
10	Incorrect	1600 ms	22128 KB	Output isn't correct
11	Incorrect	2043 ms	13532 KB	Output isn't correct
12	Incorrect	730 ms	14916 KB	Output isn't correct
13	Incorrect	938 ms	15680 KB	Output isn't correct
14	Incorrect	1103 ms	15216 KB	Output isn't correct
15	Incorrect	1279 ms	22528 KB	Output isn't correct
16	Incorrect	1495 ms	33608 KB	Output isn't correct
17	Incorrect	1483 ms	31100 KB	Output isn't correct