Submission #118825

#	Time	Username	Problem	Language	Result	Execution time	Memory
118825		wilwxk	Regions (IOI09_regions)	C++11	0 / 100	104 ms	35524 KiB

regions

#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e5+5;
const int MAXC=25000;
vector<int> g[MAXN];
int cor[MAXN], quer[MAXN][2];
unordered_map<int, int> m[MAXN];
map< pair<int, int>, int > resp;
int n, r, q;

void dfs(int z) {
	for(auto viz : g[z]) {
		dfs(viz);
		if(m[viz].size()>m[z].size()) swap(m[viz], m[z]);
		for(auto cur : m[viz]) m[z][cur.first]+=cur.second;
	}
	for(auto cur : m[z]) if(resp.find({cor[z], cur.first})!=resp.end()) resp[{cor[z], cur.first}]+=cur.second;
}

int main() {
	
	scanf("%d %d %d", &n, &r, &q);
	scanf("%d", &cor[1]); m[1][cor[1]]=1;
	for(int i=2; i<=n; i++) {
		int a, b; scanf("%d %d", &a, &b);
		g[a].push_back(i); cor[i]=b;
		m[i][b]=1;
	}
	
	for(int i=0; i<q; i++) {
		int a, b; scanf("%d %d", &a, &b);
		quer[i][0]=a; quer[i][1]=b;
		resp[{a, b}]=0;
	}
	
	dfs(1);
	
	
	for(int i=0; i<q; i++) printf("%d\n", resp[{quer[i][0], quer[i][1]}] );
	
	
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &r, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &cor[1]); m[1][cor[1]]=1;
  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:26:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

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