oj.uz

Submission #365100

# Submission time Handle Problem Language Result Execution time Memory
365100 2021-02-10T21:49:37 Z crackersamdjam Regions (IOI09_regions) C++17
30 / 100
 4333 ms 131076 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[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 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 18 ms 19180 KB Output is correct
5 Correct 21 ms 19308 KB Output is correct
6 Correct 65 ms 23020 KB Output is correct
7 Correct 73 ms 20972 KB Output is correct
8 Correct 100 ms 21996 KB Output is correct
9 Correct 263 ms 25964 KB Output is correct
10 Correct 750 ms 32748 KB Output is correct
11 Correct 601 ms 25580 KB Output is correct
12 Correct 1288 ms 34104 KB Output is correct
13 Correct 1665 ms 27836 KB Output is correct
14 Correct 961 ms 24940 KB Output is correct
15 Correct 1442 ms 31852 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2319 ms 29168 KB Output is correct
2 Correct 3783 ms 26984 KB Output is correct
3 Correct 4333 ms 34156 KB Output is correct
4 Runtime error 862 ms 131072 KB Execution killed with signal 9
5 Runtime error 825 ms 131076 KB Execution killed with signal 9
6 Runtime error 961 ms 131076 KB Execution killed with signal 9
7 Runtime error 781 ms 131076 KB Execution killed with signal 9
8 Runtime error 727 ms 131076 KB Execution killed with signal 9
9 Runtime error 742 ms 131076 KB Execution killed with signal 9
10 Runtime error 767 ms 131076 KB Execution killed with signal 9
11 Runtime error 851 ms 131076 KB Execution killed with signal 9
12 Runtime error 798 ms 131076 KB Execution killed with signal 9
13 Runtime error 812 ms 131076 KB Execution killed with signal 9
14 Runtime error 907 ms 131076 KB Execution killed with signal 9
15 Runtime error 839 ms 131076 KB Execution killed with signal 9
16 Runtime error 648 ms 131076 KB Execution killed with signal 9
17 Runtime error 851 ms 131076 KB Execution killed with signal 9