oj.uz

Submission #365107

# Submission time Handle Problem Language Result Execution time Memory
365107 2021-02-10T21:57:32 Z crackersamdjam Regions (IOI09_regions) C++17
100 / 100
 7485 ms 107628 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

using namespace std;
const int MM = 2e5+5, 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];

map<pair<int, int>, int> ans;
vector<int> big;

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: big)
			ans[{i, val[cur]}] += parcnt[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: big)
		ans[{val[cur], i}] += cnt[cur][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)
			big.emplace_back(i);
	}

	dfs(1, 0);

	for(int i = 0,a,b; i < q; i++){
		cin>>a>>b;
		if(size(nodes[a]) > SQ or size(nodes[b]) > SQ){
			cout<<ans[{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
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19180 KB Output is correct
2 Correct 13 ms 19180 KB Output is correct
3 Correct 15 ms 19180 KB Output is correct
4 Correct 17 ms 19180 KB Output is correct
5 Correct 20 ms 19180 KB Output is correct
6 Correct 32 ms 19308 KB Output is correct
7 Correct 46 ms 19308 KB Output is correct
8 Correct 60 ms 19308 KB Output is correct
9 Correct 71 ms 20204 KB Output is correct
10 Correct 111 ms 19948 KB Output is correct
11 Correct 172 ms 20232 KB Output is correct
12 Correct 199 ms 21100 KB Output is correct
13 Correct 314 ms 20204 KB Output is correct
14 Correct 428 ms 20972 KB Output is correct
15 Correct 473 ms 27500 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1993 ms 25856 KB Output is correct
2 Correct 2031 ms 23404 KB Output is correct
3 Correct 3823 ms 29732 KB Output is correct
4 Correct 373 ms 21484 KB Output is correct
5 Correct 598 ms 25452 KB Output is correct
6 Correct 2148 ms 23608 KB Output is correct
7 Correct 2840 ms 24684 KB Output is correct
8 Correct 2708 ms 36288 KB Output is correct
9 Correct 4258 ms 31980 KB Output is correct
10 Correct 7213 ms 45036 KB Output is correct
11 Correct 7485 ms 30956 KB Output is correct
12 Correct 2367 ms 35828 KB Output is correct
13 Correct 3294 ms 37024 KB Output is correct
14 Correct 5416 ms 79388 KB Output is correct
15 Correct 5593 ms 50432 KB Output is correct
16 Correct 6012 ms 68332 KB Output is correct
17 Correct 7127 ms 107628 KB Output is correct