Submission #526306

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526306	2022-02-14T08:51:45 Z	1ne	Regions (IOI09_regions)	C++14	0 / 100	95 ms	33552 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());
}
vector<int>output;
for (int i = 0;i<q;++i){
	int x,y;cin>>x>>y;
	--x;
	--y;
	if (x==region[0]){
		output.push_back(region_count[y]);
		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;
	}
	output.push_back(ans-ans2+1);
}
for (auto x:output){
	cout<<x<<endl;
}
return 0;}

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1 ms	200 KB	Time limit exceeded (wall clock)
2	Execution timed out	1 ms	200 KB	Time limit exceeded (wall clock)
3	Execution timed out	0 ms	200 KB	Time limit exceeded (wall clock)
4	Execution timed out	1 ms	200 KB	Time limit exceeded (wall clock)
5	Execution timed out	1 ms	328 KB	Time limit exceeded (wall clock)
6	Execution timed out	1 ms	328 KB	Time limit exceeded (wall clock)
7	Execution timed out	1 ms	328 KB	Time limit exceeded (wall clock)
8	Execution timed out	1 ms	456 KB	Time limit exceeded (wall clock)
9	Execution timed out	2 ms	1096 KB	Time limit exceeded (wall clock)
10	Execution timed out	3 ms	968 KB	Time limit exceeded (wall clock)
11	Execution timed out	4 ms	1480 KB	Time limit exceeded (wall clock)
12	Execution timed out	5 ms	2120 KB	Time limit exceeded (wall clock)
13	Execution timed out	7 ms	1736 KB	Time limit exceeded (wall clock)
14	Execution timed out	11 ms	2376 KB	Time limit exceeded (wall clock)
15	Execution timed out	12 ms	7056 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	23 ms	6992 KB	Time limit exceeded (wall clock)
2	Execution timed out	22 ms	5320 KB	Time limit exceeded (wall clock)
3	Execution timed out	25 ms	10032 KB	Time limit exceeded (wall clock)
4	Execution timed out	9 ms	2572 KB	Time limit exceeded (wall clock)
5	Execution timed out	11 ms	5444 KB	Time limit exceeded (wall clock)
6	Execution timed out	15 ms	4552 KB	Time limit exceeded (wall clock)
7	Execution timed out	22 ms	5832 KB	Time limit exceeded (wall clock)
8	Execution timed out	30 ms	14324 KB	Time limit exceeded (wall clock)
9	Execution timed out	49 ms	13256 KB	Time limit exceeded (wall clock)
10	Execution timed out	53 ms	22036 KB	Time limit exceeded (wall clock)
11	Execution timed out	65 ms	13492 KB	Time limit exceeded (wall clock)
12	Execution timed out	69 ms	14860 KB	Time limit exceeded (wall clock)
13	Execution timed out	62 ms	15800 KB	Time limit exceeded (wall clock)
14	Execution timed out	79 ms	15200 KB	Time limit exceeded (wall clock)
15	Execution timed out	62 ms	22452 KB	Time limit exceeded (wall clock)
16	Execution timed out	95 ms	33552 KB	Time limit exceeded (wall clock)
17	Execution timed out	86 ms	31104 KB	Time limit exceeded (wall clock)