oj.uz

Submission #365098

# Submission time Handle Problem Language Result Execution time Memory
365098 2021-02-10T21:46:57 Z crackersamdjam Regions (IOI09_regions) C++17
55 / 100
 7888 ms 90620 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;
using ll = long long;
const int MM = 2e5+5, SQ = 500;
// const int MM = 2e5+5, SQ = 0;

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

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

	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);
			ll 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 13 ms 19180 KB Output is correct
2 Correct 13 ms 19180 KB Output is correct
3 Correct 16 ms 19180 KB Output is correct
4 Correct 20 ms 19180 KB Output is correct
5 Correct 18 ms 19308 KB Output is correct
6 Correct 32 ms 19308 KB Output is correct
7 Correct 43 ms 19308 KB Output is correct
8 Correct 51 ms 19308 KB Output is correct
9 Correct 71 ms 20332 KB Output is correct
10 Correct 144 ms 19948 KB Output is correct
11 Correct 174 ms 20204 KB Output is correct
12 Correct 217 ms 21228 KB Output is correct
13 Correct 289 ms 20204 KB Output is correct
14 Correct 434 ms 21228 KB Output is correct
15 Correct 456 ms 28780 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1889 ms 26268 KB Output isn't correct
2 Incorrect 2169 ms 23284 KB Output isn't correct
3 Incorrect 3726 ms 30700 KB Output isn't correct
4 Correct 434 ms 21740 KB Output is correct
5 Correct 585 ms 26348 KB Output is correct
6 Correct 2084 ms 24172 KB Output is correct
7 Correct 2715 ms 25324 KB Output is correct
8 Correct 2901 ms 38892 KB Output is correct
9 Correct 4571 ms 33260 KB Output is correct
10 Correct 7572 ms 48876 KB Output is correct
11 Correct 7888 ms 32364 KB Output is correct
12 Incorrect 2709 ms 34944 KB Output isn't correct
13 Incorrect 3323 ms 37692 KB Output isn't correct
14 Incorrect 4398 ms 58420 KB Output isn't correct
15 Incorrect 5447 ms 51768 KB Output isn't correct
16 Incorrect 5742 ms 74780 KB Output isn't correct
17 Incorrect 6809 ms 90620 KB Output isn't correct