Submission #365119

#	Time	Username	Problem	Language	Result	Execution time	Memory
365119		crackersamdjam	Regions (IOI09_regions)	C++17	100 / 100	5798 ms	85740 KiB

regions

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args>
void pr(Args... args){}
#endif

using namespace std;
constexpr int MM = 2e5+1, NN = 25001, SQ = 450;

int n, m, q;
int val[MM];
vector<int> adj[MM];
int in[MM], out[MM], t;
vector<int> nodes[MM], pos[MM];
int bid[MM];
vector<int> big;

int parcnt[NN], sub[MM];

int ans1[SQ][NN];
int ans2[NN][SQ];

void dfs(int cur, int pre){
	in[cur] = ++t;
	pos[val[cur]].emplace_back(t);
	if(size(nodes[val[cur]]) < SQ){
		//do big to small only
		for(int i = 0; i < size(big); i++)
			ans1[i][val[cur]] += parcnt[big[i]];
	}
	parcnt[val[cur]]++;

	for(auto u: adj[cur]){
		if(u != pre)
			dfs(u, cur);
	}

	parcnt[val[cur]]--;
	out[cur] = t;
}

void go(int cur, int pre, int col){
	sub[cur] = val[cur] == col;
	for(auto u: adj[cur]){
		if(u != pre){
			go(u, cur, col);
			sub[cur] += sub[u];
		}
	}
	//do small to big and big to big
	ans2[val[cur]][bid[col]] += sub[cur];
	// pr("two", val[cur], col, sub[cur], ans2[val[cur]][bid[col]]);
}

int main(){
	cin>>n>>m>>q;
	cin>>val[1];
	nodes[val[1]].emplace_back(1);
	for(int i = 2,p; i <= n; i++){
		cin>>p>>val[i];
		adj[p].emplace_back(i);
		nodes[val[i]].emplace_back(i);
	}

	for(int i = 1; i <= m; i++){
		if(size(nodes[i]) >= SQ){
			bid[i] = size(big);
			big.emplace_back(i);
		}
		pos[i].reserve(size(nodes[i]));
	}

	dfs(1, 0);

	for(int i = 0; i < size(big); i++){
		go(1, 0, big[i]);
	}

	for(int i = 0,a,b; i < q; i++){
		cin>>a>>b;
		if(size(nodes[b]) >= SQ){
			cout<<ans2[a][bid[b]]<<'\n';
		}
		else if(size(nodes[a]) >= SQ){
			cout<<ans1[bid[a]][b]<<'\n';
		}
		else{
			int ret = 0;
			for(int j: nodes[a])
				ret += upper_bound(all(pos[b]), out[j]) - upper_bound(all(pos[b]), in[j]);
			cout<<ret<<'\n';
		}
		cout<<flush;
	}
}
/*
precompute big-small, small-small, small-big
brute force small-small
*/

Compilation message (stderr)

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i = 0; i < size(big); i++)
      |                  ~~^~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i = 0; i < size(big); i++){
      |                 ~~^~~~~~~~~~~

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