Submission #365110

#	Time	Username	Problem	Language	Result	Execution time	Memory
365110		crackersamdjam	Regions (IOI09_regions)	C++17	90 / 100	7629 ms	111212 KiB

regions

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

using namespace std;
const int MM = 2e5+5, NN = 25000, SQ = 500;

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

int ans1[SQ][NN];
int ans2[NN][SQ]; //swap order if still not fast enough

void update(int i, int v){
	for(; i < MM; i += i&-i)
		bit[i] += v;
}

int query(int i){
	int v = 0;
	for(; i; i -= i&-i)
		v += bit[i];
	return v;
}

void dfs(int cur, int pre){
	in[cur] = ++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]]++;

	int id = 0;
	for(auto u: adj[cur]){
		if(u != pre){
			dfs(u, cur);
			if(size(cnt[u]) > size(cnt[id]))
				id = u;
		}
	}
	cnt[cur] = move(cnt[id]);
	for(auto u: adj[cur]){
		if(u != pre and u != id){
			for(auto [a, c]: cnt[u]){
				cnt[cur][a] += c;
			}
			cnt[u].clear();
		}
	}
	cnt[cur][val[cur]]++;

	//do small to big and big to big
	for(int i = 0; i < size(big); i++)
		ans2[val[cur]][i] += cnt[cur][big[i]];

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

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);
		}
	}

	dfs(1, 0);

	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{
			for(int j: nodes[b])
				update(in[j], 1);
			
			int ret = 0;
			for(int j: nodes[a])
				ret += query(out[j]) - query(in[j]-1);
			
			for(int j: nodes[b])
				update(in[j], -1);

			cout<<ret<<'\n';
		}
	}
}
/*
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:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i = 0; i < size(big); i++)
      |                 ~~^~~~~~~~~~~

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