Submission #526433

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526433	2022-02-14T18:32:35 Z	1ne	Regions (IOI09_regions)	C++14	13 / 100	1113 ms	131076 KB

regions

#include<bits/stdc++.h>
using namespace std;
 
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int64_t n,r,q;cin>>n>>r>>q;
vector<int64_t>region(n,-1),parent(n,-1);
cin>>region[0];
region[0]--;
vector<vector<int64_t>>adj(n);
for (int64_t i = 1;i<n;++i){
	cin>>parent[i]>>region[i];
	parent[i]--;
	adj[parent[i]].push_back(i);
	region[i]--;
}
 
vector<vector<int64_t>>arr(r);
vector<bool>visited(n,false);
for (int64_t i = 0;i<n;++i){
	if (visited[i]){
		continue;
	}
	vector<int64_t>region_count(r,0);
	function<void(int64_t)> dfs = [&](int64_t cur){
		if (visited[cur]){
			return;
		}
		visited[cur]=true;
		for (int j = 0;j<r;++j){
			for (int k = 0;k<region_count[j];++k){
				arr[j].push_back(region[cur]);
			}
		}
		region_count[region[cur]]++;
		for (auto x:adj[cur]){
			dfs(x);
		}
		region_count[region[cur]]--;
	};
	dfs(i);
}
for (int64_t i = 0;i<r;++i){
	sort(arr[i].begin(),arr[i].end());
}
for (int64_t i = 0;i<q;++i){
	int64_t x,y;cin>>x>>y;
	--x;
	--y;
	if (arr[x].empty()){
		cout<<0<<endl;
		continue;
	}
	int64_t ans = 0;
	int64_t left = 0,right = arr[x].size()-1;
	while(left<=right){
		int64_t mid = (left + right)>>1;
		if (arr[x][mid]<=y){
			left = mid + 1;
		}
		else{
			right = mid - 1;
		}
		if (arr[x][mid]==y){
			ans = max(ans,mid);
		}
	}
	int64_t ans2 = INT_MAX;
	int64_t left2 = 0,right2 = arr[x].size()-1;
	while(left2<=right2){
		int64_t mid = (left2 + right2)>>1;
		if (arr[x][mid]>=y){
			right2 = mid - 1;
		}
		else left2 = mid + 1;
		if (arr[x][mid]==y){
			ans2 = min(ans2,mid);
		}
	}
	cout<<max(ans - ans2 + 1,(int64_t)0)<<endl;
	
}
return 0;}

Subtask #1

13.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	2 ms	200 KB	Output is correct
4	Correct	5 ms	328 KB	Output is correct
5	Correct	9 ms	712 KB	Output is correct
6	Correct	22 ms	4116 KB	Output is correct
7	Correct	46 ms	1432 KB	Output is correct
8	Correct	51 ms	3528 KB	Output is correct
9	Correct	459 ms	124560 KB	Output is correct
10	Correct	143 ms	12580 KB	Output is correct
11	Correct	324 ms	46700 KB	Output is correct
12	Runtime error	172 ms	131076 KB	Execution killed with signal 9
13	Correct	227 ms	7988 KB	Output is correct
14	Correct	383 ms	52636 KB	Output is correct
15	Runtime error	179 ms	131076 KB	Execution killed with signal 9

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	159 ms	131076 KB	Execution killed with signal 9
2	Runtime error	164 ms	131076 KB	Execution killed with signal 9
3	Runtime error	169 ms	131076 KB	Execution killed with signal 9
4	Runtime error	296 ms	131076 KB	Execution killed with signal 9
5	Runtime error	258 ms	131076 KB	Execution killed with signal 9
6	Runtime error	381 ms	131072 KB	Execution killed with signal 9
7	Runtime error	462 ms	131076 KB	Execution killed with signal 9
8	Runtime error	354 ms	131076 KB	Execution killed with signal 9
9	Runtime error	466 ms	131076 KB	Execution killed with signal 9
10	Runtime error	493 ms	131076 KB	Execution killed with signal 9
11	Runtime error	1113 ms	131076 KB	Execution killed with signal 9
12	Runtime error	692 ms	131076 KB	Execution killed with signal 9
13	Runtime error	623 ms	131076 KB	Execution killed with signal 9
14	Runtime error	821 ms	131076 KB	Execution killed with signal 9
15	Runtime error	527 ms	131076 KB	Execution killed with signal 9
16	Runtime error	507 ms	131076 KB	Execution killed with signal 9
17	Runtime error	484 ms	131076 KB	Execution killed with signal 9