Submission #526426

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526426	2022-02-14T17:59:44 Z	1ne	Regions (IOI09_regions)	C++14	0 / 100	2357 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>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[par]].push_back(region[x]);
		dfs(x,par);
	}
};
for (int i = 1;i<n;++i){
	//if (!visited[i])
		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;
	}
	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

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	1 ms	200 KB	Output isn't correct
4	Incorrect	1 ms	200 KB	Output isn't correct
5	Incorrect	9 ms	456 KB	Output isn't correct
6	Incorrect	21 ms	2120 KB	Output isn't correct
7	Incorrect	33 ms	840 KB	Output isn't correct
8	Incorrect	41 ms	1968 KB	Output isn't correct
9	Incorrect	773 ms	62040 KB	Output isn't correct
10	Incorrect	141 ms	6080 KB	Output isn't correct
11	Incorrect	383 ms	23532 KB	Output isn't correct
12	Runtime error	532 ms	131076 KB	Execution killed with signal 9
13	Incorrect	182 ms	4712 KB	Output isn't correct
14	Incorrect	517 ms	25384 KB	Output isn't correct
15	Runtime error	516 ms	131076 KB	Execution killed with signal 9

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	724 ms	131076 KB	Execution killed with signal 9
2	Runtime error	701 ms	131076 KB	Execution killed with signal 9
3	Runtime error	619 ms	131076 KB	Execution killed with signal 9
4	Runtime error	735 ms	131076 KB	Execution killed with signal 9
5	Runtime error	493 ms	131072 KB	Execution killed with signal 9
6	Runtime error	764 ms	131076 KB	Execution killed with signal 9
7	Runtime error	838 ms	131076 KB	Execution killed with signal 9
8	Runtime error	576 ms	131076 KB	Execution killed with signal 9
9	Runtime error	1797 ms	131076 KB	Execution killed with signal 9
10	Runtime error	650 ms	131076 KB	Execution killed with signal 9
11	Runtime error	1462 ms	131076 KB	Execution killed with signal 9
12	Runtime error	2357 ms	131076 KB	Execution killed with signal 9
13	Runtime error	1527 ms	131076 KB	Execution killed with signal 9
14	Runtime error	2050 ms	131076 KB	Execution killed with signal 9
15	Runtime error	818 ms	131076 KB	Execution killed with signal 9
16	Runtime error	674 ms	131076 KB	Execution killed with signal 9
17	Runtime error	595 ms	131076 KB	Execution killed with signal 9