oj.uz

Submission #526440

# Submission time Handle Problem Language Result Execution time Memory
526440 2022-02-14T18:46:17 Z 1ne Regions (IOI09_regions) C++14
12 / 100
 617 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);
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){
		if (j!=region[cur])
			arr[j].push_back({region[cur],region_count[j]});
	}
	region_count[region[cur]]++;
	for (auto x:adj[cur]){
		if (!visited[x])
			dfs(x);
	}
	region_count[region[cur]]--;
};

for (int64_t i = 0;i<n;++i){
	if (!visited[i]){
		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<INT_MAX){
		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:45: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]
   45 |  for (int j = 1;j<arr[i].size();++j){
      |                 ~^~~~~~~~~~~~~~

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 4 ms 456 KB Output is correct
5 Correct 9 ms 784 KB Output is correct
6 Correct 33 ms 4808 KB Output is correct
7 Correct 49 ms 5416 KB Output is correct
8 Correct 58 ms 7356 KB Output is correct
9 Correct 183 ms 34880 KB Output is correct
10 Correct 445 ms 81708 KB Output is correct
11 Correct 486 ms 70092 KB Output is correct
12 Runtime error 167 ms 131076 KB Execution killed with signal 9
13 Runtime error 175 ms 131076 KB Execution killed with signal 9
14 Correct 617 ms 100948 KB Output is correct
15 Runtime error 196 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 196 ms 131076 KB Execution killed with signal 9
2 Runtime error 217 ms 131076 KB Execution killed with signal 9
3 Runtime error 170 ms 131076 KB Execution killed with signal 9
4 Runtime error 147 ms 131076 KB Execution killed with signal 9
5 Runtime error 138 ms 131076 KB Execution killed with signal 9
6 Runtime error 153 ms 131076 KB Execution killed with signal 9
7 Runtime error 138 ms 131076 KB Execution killed with signal 9
8 Runtime error 134 ms 131076 KB Execution killed with signal 9
9 Runtime error 153 ms 131076 KB Execution killed with signal 9
10 Runtime error 176 ms 131076 KB Execution killed with signal 9
11 Runtime error 205 ms 131076 KB Execution killed with signal 9
12 Runtime error 151 ms 131076 KB Execution killed with signal 9
13 Runtime error 146 ms 131076 KB Execution killed with signal 9
14 Runtime error 160 ms 131076 KB Execution killed with signal 9
15 Runtime error 182 ms 131076 KB Execution killed with signal 9
16 Runtime error 186 ms 131076 KB Execution killed with signal 9
17 Runtime error 171 ms 131076 KB Execution killed with signal 9