Submission #526412

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526412	2022-02-14T17:37:45 Z	1ne	Regions (IOI09_regions)	C++14	0 / 100	1785 ms	33620 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);
vector<bool>op(r,false);
op[region[0]]=true;
function<void(int , int)> dfs = [&](int cur,int par){
	visited[cur] = true;
	for (auto x:adj[cur]){
		if (x==par)continue;
		if (x==0){
			op[region[x]]=true;
			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 (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(0,ans - ans2 + 1)<<endl;
	
}
return 0;}

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 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	19 ms	456 KB	Output isn't correct
7	Incorrect	43 ms	328 KB	Output isn't correct
8	Incorrect	27 ms	456 KB	Output isn't correct
9	Incorrect	47 ms	1096 KB	Output isn't correct
10	Incorrect	79 ms	968 KB	Output isn't correct
11	Incorrect	111 ms	1480 KB	Output isn't correct
12	Incorrect	117 ms	2220 KB	Output isn't correct
13	Incorrect	99 ms	1744 KB	Output isn't correct
14	Incorrect	146 ms	2452 KB	Output isn't correct
15	Incorrect	184 ms	6984 KB	Output isn't correct

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	704 ms	7048 KB	Output isn't correct
2	Incorrect	922 ms	5364 KB	Output isn't correct
3	Incorrect	1278 ms	10040 KB	Output isn't correct
4	Incorrect	233 ms	2632 KB	Output isn't correct
5	Incorrect	302 ms	5452 KB	Output isn't correct
6	Incorrect	460 ms	4576 KB	Output isn't correct
7	Incorrect	724 ms	5824 KB	Output isn't correct
8	Incorrect	758 ms	14332 KB	Output isn't correct
9	Incorrect	1189 ms	13364 KB	Output isn't correct
10	Incorrect	1322 ms	22148 KB	Output isn't correct
11	Incorrect	1651 ms	13536 KB	Output isn't correct
12	Incorrect	883 ms	14880 KB	Output isn't correct
13	Incorrect	1061 ms	15768 KB	Output isn't correct
14	Incorrect	1051 ms	15140 KB	Output isn't correct
15	Incorrect	1569 ms	22532 KB	Output isn't correct
16	Incorrect	1543 ms	33620 KB	Output isn't correct
17	Incorrect	1785 ms	31112 KB	Output isn't correct