oj.uz

Submission #526438

# Submission time Handle Problem Language Result Execution time Memory
526438 2022-02-14T18:42:05 Z 1ne Regions (IOI09_regions) C++14
12 / 100
 650 ms 131076 KB 
#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<pair<int64_t,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){
			arr[j].push_back({region[cur],region_count[j]});
		}
		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 (int j = 1;j<arr[i].size();++j){
		arr[i][j].second+=arr[i][j-1].second;
	}
}
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 = -1;
	int64_t left = 0,right = arr[x].size()-1;
	while(left<=right){
		int64_t mid = (left + right)>>1;
		if (arr[x][mid].first<=y){
			left = mid + 1;
		}
		else{
			right = mid - 1;
		}
		if (arr[x][mid].first==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].first>=y){
			right2 = mid - 1;
		}
		else left2 = mid + 1;
		if (arr[x][mid].first==y){
			ans2 = min(ans2,mid);
		}
	}
	int64_t ans3 = 0;
	if (ans>=0){
		ans3+=arr[x][ans].second;
	}
	if (ans2>0&&ans2<arr[x].size()){
		ans3-=arr[x][ans2-1].second;
	}
	cout<<max(ans3,(int64_t)0)<<endl;
	
}
return 0;}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (int j = 1;j<arr[i].size();++j){
      |                 ~^~~~~~~~~~~~~~
regions.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  if (ans2>0&&ans2<arr[x].size()){
      |              ~~~~^~~~~~~~~~~~~~

Subtask #1
12.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 328 KB Output is correct
4 Correct 5 ms 488 KB Output is correct
5 Correct 9 ms 712 KB Output is correct
6 Correct 27 ms 4528 KB Output is correct
7 Correct 44 ms 5064 KB Output is correct
8 Correct 67 ms 6984 KB Output is correct
9 Correct 195 ms 32704 KB Output is correct
10 Correct 430 ms 79200 KB Output is correct
11 Correct 433 ms 67276 KB Output is correct
12 Runtime error 179 ms 131076 KB Execution killed with signal 9
13 Runtime error 183 ms 131076 KB Execution killed with signal 9
14 Correct 650 ms 98608 KB Output is correct
15 Runtime error 175 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 207 ms 131076 KB Execution killed with signal 9
2 Runtime error 250 ms 131076 KB Execution killed with signal 9
3 Runtime error 182 ms 131076 KB Execution killed with signal 9
4 Runtime error 159 ms 131076 KB Execution killed with signal 9
5 Runtime error 134 ms 131076 KB Execution killed with signal 9
6 Runtime error 151 ms 131076 KB Execution killed with signal 9
7 Runtime error 138 ms 131076 KB Execution killed with signal 9
8 Runtime error 144 ms 131076 KB Execution killed with signal 9
9 Runtime error 143 ms 131076 KB Execution killed with signal 9
10 Runtime error 172 ms 131076 KB Execution killed with signal 9
11 Runtime error 179 ms 131076 KB Execution killed with signal 9
12 Runtime error 149 ms 131076 KB Execution killed with signal 9
13 Runtime error 146 ms 131076 KB Execution killed with signal 9
14 Runtime error 191 ms 131076 KB Execution killed with signal 9
15 Runtime error 174 ms 131076 KB Execution killed with signal 9
16 Runtime error 189 ms 131076 KB Execution killed with signal 9
17 Runtime error 161 ms 131076 KB Execution killed with signal 9