oj.uz

Submission #365096

# Submission time Handle Problem Language Result Execution time Memory
365096 2021-02-10T21:45:45 Z crackersamdjam Regions (IOI09_regions) C++17
30 / 100
 4206 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*2];

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 14 ms 19180 KB Output is correct
4 Correct 18 ms 19180 KB Output is correct
5 Correct 25 ms 19308 KB Output is correct
6 Correct 69 ms 23020 KB Output is correct
7 Correct 84 ms 20972 KB Output is correct
8 Correct 118 ms 21996 KB Output is correct
9 Correct 247 ms 26220 KB Output is correct
10 Correct 772 ms 32748 KB Output is correct
11 Correct 665 ms 25580 KB Output is correct
12 Correct 1339 ms 34028 KB Output is correct
13 Correct 1771 ms 27756 KB Output is correct
14 Correct 1000 ms 24812 KB Output is correct
15 Correct 1471 ms 32312 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2691 ms 29224 KB Output is correct
2 Correct 3959 ms 26900 KB Output is correct
3 Correct 4206 ms 34704 KB Output is correct
4 Runtime error 843 ms 131076 KB Execution killed with signal 9
5 Runtime error 766 ms 131072 KB Execution killed with signal 9
6 Runtime error 947 ms 131072 KB Execution killed with signal 9
7 Runtime error 738 ms 131076 KB Execution killed with signal 9
8 Runtime error 721 ms 131072 KB Execution killed with signal 9
9 Runtime error 720 ms 131076 KB Execution killed with signal 9
10 Runtime error 763 ms 131076 KB Execution killed with signal 9
11 Runtime error 841 ms 131072 KB Execution killed with signal 9
12 Runtime error 756 ms 131076 KB Execution killed with signal 9
13 Runtime error 823 ms 131076 KB Execution killed with signal 9
14 Runtime error 830 ms 131076 KB Execution killed with signal 9
15 Runtime error 893 ms 131072 KB Execution killed with signal 9
16 Runtime error 638 ms 131072 KB Execution killed with signal 9
17 Runtime error 808 ms 131076 KB Execution killed with signal 9