oj.uz

Submission #365101

# Submission time Handle Problem Language Result Execution time Memory
365101 2021-02-10T21:50:01 Z crackersamdjam Regions (IOI09_regions) C++17
95 / 100
 8000 ms 110748 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;

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[val[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[val[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

smol-smol ac
big-big ac
big-smol wa

*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19324 KB Output is correct
2 Correct 14 ms 19180 KB Output is correct
3 Correct 14 ms 19180 KB Output is correct
4 Correct 20 ms 19180 KB Output is correct
5 Correct 25 ms 19180 KB Output is correct
6 Correct 47 ms 19308 KB Output is correct
7 Correct 45 ms 19308 KB Output is correct
8 Correct 49 ms 19308 KB Output is correct
9 Correct 82 ms 20332 KB Output is correct
10 Correct 129 ms 19948 KB Output is correct
11 Correct 225 ms 20204 KB Output is correct
12 Correct 184 ms 21204 KB Output is correct
13 Correct 322 ms 20204 KB Output is correct
14 Correct 427 ms 21100 KB Output is correct
15 Correct 456 ms 28140 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2166 ms 26176 KB Output is correct
2 Correct 2301 ms 23432 KB Output is correct
3 Correct 4169 ms 30352 KB Output is correct
4 Correct 475 ms 21612 KB Output is correct
5 Correct 595 ms 25964 KB Output is correct
6 Correct 2058 ms 24004 KB Output is correct
7 Correct 2876 ms 25196 KB Output is correct
8 Correct 3042 ms 37740 KB Output is correct
9 Correct 4289 ms 32988 KB Output is correct
10 Correct 7263 ms 47468 KB Output is correct
11 Correct 7856 ms 32236 KB Output is correct
12 Correct 2568 ms 36404 KB Output is correct
13 Correct 3547 ms 37868 KB Output is correct
14 Correct 6291 ms 79772 KB Output is correct
15 Correct 5992 ms 52716 KB Output is correct
16 Correct 5827 ms 72296 KB Output is correct
17 Execution timed out 8010 ms 110748 KB Time limit exceeded