oj.uz

Submission #365105

# Submission time Handle Problem Language Result Execution time Memory
365105 2021-02-10T21:54:39 Z crackersamdjam Regions (IOI09_regions) C++17
15 / 100
 6782 ms 131076 KB 
#include <bits/stdc++.h>
#define aint(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;
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 = 1; i <= m; i++)
		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 14 ms 19180 KB Output is correct
3 Correct 15 ms 19180 KB Output is correct
4 Correct 18 ms 19308 KB Output is correct
5 Correct 26 ms 19308 KB Output is correct
6 Correct 63 ms 23148 KB Output is correct
7 Correct 86 ms 20844 KB Output is correct
8 Correct 99 ms 22124 KB Output is correct
9 Correct 286 ms 25836 KB Output is correct
10 Correct 728 ms 32332 KB Output is correct
11 Correct 745 ms 25484 KB Output is correct
12 Correct 1368 ms 33732 KB Output is correct
13 Correct 1698 ms 27724 KB Output is correct
14 Correct 1215 ms 24556 KB Output is correct
15 Correct 1695 ms 31212 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 3584 ms 28864 KB Output isn't correct
2 Incorrect 4525 ms 26620 KB Output isn't correct
3 Incorrect 6782 ms 33796 KB Output isn't correct
4 Runtime error 757 ms 131076 KB Execution killed with signal 9
5 Runtime error 637 ms 131076 KB Execution killed with signal 9
6 Runtime error 841 ms 131076 KB Execution killed with signal 9
7 Runtime error 694 ms 131076 KB Execution killed with signal 9
8 Runtime error 745 ms 131076 KB Execution killed with signal 9
9 Runtime error 688 ms 131072 KB Execution killed with signal 9
10 Runtime error 750 ms 131076 KB Execution killed with signal 9
11 Runtime error 823 ms 131076 KB Execution killed with signal 9
12 Runtime error 738 ms 131076 KB Execution killed with signal 9
13 Runtime error 769 ms 131076 KB Execution killed with signal 9
14 Runtime error 743 ms 131076 KB Execution killed with signal 9
15 Runtime error 775 ms 131076 KB Execution killed with signal 9
16 Runtime error 662 ms 131076 KB Execution killed with signal 9
17 Runtime error 761 ms 131076 KB Execution killed with signal 9