Submission #526442

#	Time	Username	Problem	Language	Result	Execution time	Memory
526442		1ne	Regions (IOI09_regions)	C++14	30 / 100	3742 ms	131076 KiB

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<pair<int64_t,int64_t>>>arr(r);
vector<bool>visited(n,false);
vector<int64_t>region_count(r,0);
vector<map<int64_t,int64_t>>brr(r);
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]&&region_count[j]>0)
			brr[j][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;
	cout<<brr[x][y]<<endl;
}
return 0;}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:46: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]
   46 |  for (int j = 1;j<arr[i].size();++j){
      |                 ~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 85