oj.uz

Submission #365090

# Submission time Handle Problem Language Result Execution time Memory
365090 2021-02-10T21:30:49 Z crackersamdjam Regions (IOI09_regions) C++17
55 / 100
 7471 ms 110192 KB 
#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;
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, smol;

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;
	parcnt[val[cur]]++;
	if(size(nodes[cur]) <= SQ){
		for(int i: big)
			ans[{i, val[cur]}] += parcnt[i];
	}

	int id = 0;
	for(auto u: adj[cur]){
		if(u == pre) continue;
		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) continue;
		if(u != id){
			for(auto [a, c]: cnt[u]){
				cnt[cur][a] += c;
			}
			cnt[u].clear();
			// cnt[u].shrink_to_fit();
		}
	}
	cnt[cur][val[cur]]++;

	if(size(nodes[cur]) <= SQ){
		for(int i: big)
			ans[{val[cur], i}] += cnt[cur][i];
	}
	else{
		//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);
		}
		else{
			smol.emplace_back(i);
		}
	}
	dfs(1, 0);
	for(int i = 0,a,b; i < q; i++){
		cin>>a>>b;
		assert(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';
		}
	}
}
/*
I need online solution...
I precompute all small-large and all large-large

*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19180 KB Output is correct
2 Correct 12 ms 19180 KB Output is correct
3 Correct 14 ms 19180 KB Output is correct
4 Correct 16 ms 19180 KB Output is correct
5 Correct 19 ms 19180 KB Output is correct
6 Correct 22 ms 19308 KB Output is correct
7 Correct 43 ms 19308 KB Output is correct
8 Correct 45 ms 19308 KB Output is correct
9 Correct 54 ms 20332 KB Output is correct
10 Correct 117 ms 19820 KB Output is correct
11 Correct 148 ms 20204 KB Output is correct
12 Correct 186 ms 21228 KB Output is correct
13 Correct 278 ms 20204 KB Output is correct
14 Correct 465 ms 20972 KB Output is correct
15 Correct 479 ms 28396 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2072 ms 26092 KB Output isn't correct
2 Incorrect 2320 ms 23448 KB Output isn't correct
3 Incorrect 3694 ms 30260 KB Output isn't correct
4 Correct 444 ms 21484 KB Output is correct
5 Correct 439 ms 25836 KB Output is correct
6 Correct 2005 ms 23660 KB Output is correct
7 Correct 2743 ms 24812 KB Output is correct
8 Correct 2848 ms 37356 KB Output is correct
9 Correct 4182 ms 32312 KB Output is correct
10 Correct 7393 ms 46572 KB Output is correct
11 Correct 7471 ms 31140 KB Output is correct
12 Incorrect 2310 ms 35720 KB Output isn't correct
13 Incorrect 3535 ms 37356 KB Output isn't correct
14 Incorrect 6128 ms 79636 KB Output isn't correct
15 Incorrect 5496 ms 51564 KB Output isn't correct
16 Incorrect 5809 ms 71532 KB Output isn't correct
17 Incorrect 7059 ms 110192 KB Output isn't correct