Submission #293343

#	Time	Username	Problem	Language	Result	Execution time	Memory
293343		Plurm	Regions (IOI09_regions)	C++11	100 / 100	5546 ms	117588 KiB

regions

#include <bits/stdc++.h>
using namespace std;
const int K = 2000;
vector<int> sp; // special regions
vector<int> bckt[25005];
int h[200005];
int s[200005];
int stat[200005][200005/K+10];
int cnt[200005]; // how many parents with i-th region
vector<int> g[200005];
int prec[200005/K+10][25005]; // prec[i][j] -> how the i-th special regions manage ones from j-th region
vector<int> et;
vector<int> etbckt[25005];
int st[200005];
int ft[200005];
void dfs(int u){
	st[u] = et.size();
	etbckt[h[u]].push_back(et.size());
	et.push_back(u);
	for(int i = 0; i < sp.size(); i++){
		stat[u][i] = cnt[sp[i]];
	}
	cnt[h[u]]++;
	for(int v : g[u]){
		dfs(v);
	}
	cnt[h[u]]--;
	ft[u] = et.size();
}
int query(int r1, int r2){
	if(binary_search(sp.begin(), sp.end(), r1)){
		// special region
		return prec[lower_bound(sp.begin(), sp.end(), r1)-sp.begin()][r2];
	}else{
		// normal region
		int ans = 0;
		for(int x : bckt[r1]){
			int l = st[x];
			int r = ft[x];
			ans += lower_bound(etbckt[r2].begin(), etbckt[r2].end(), r) - lower_bound(etbckt[r2].begin(), etbckt[r2].end(), l);
		}
		return ans;
	}
}
int main(){
	int n, r, q;
	scanf("%d%d%d",&n,&r,&q);
	scanf("%d", h+1);
	bckt[h[1]].push_back(1);
	for(int i = 2; i <= n; i++){
		scanf("%d%d", s+i, h+i);
		g[s[i]].push_back(i);
		bckt[h[i]].push_back(i);
	}
	for(int i = 1; i <= r; i++){
		if(bckt[i].size() > K){
			sp.push_back(i);
		}
	}
	dfs(1);
	for(int i = 1; i <= r; i++){
		for(int u : bckt[i]){
			for(int j = 0; j < sp.size(); j++){
				prec[j][i] += stat[u][j];
			}
		}
	}
	while(q--){
		int r1, r2;
		scanf("%d%d",&r1,&r2);
		printf("%d\n", query(r1, r2));
		fflush(stdout);
	}
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(int)':
regions.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < sp.size(); i++){
      |                 ~~^~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    for(int j = 0; j < sp.size(); j++){
      |                   ~~^~~~~~~~~~~
regions.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |  scanf("%d%d%d",&n,&r,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  scanf("%d", h+1);
      |  ~~~~~^~~~~~~~~~~
regions.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d%d", s+i, h+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |   scanf("%d%d",&r1,&r2);
      |   ~~~~~^~~~~~~~~~~~~~~~

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