oj.uz

Submission #365087

# Submission time Handle Problem Language Result Execution time Memory
365087 2021-02-10T21:26:28 Z crackersamdjam Regions (IOI09_regions) C++17
15 / 100
 8000 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;
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: smol)
			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: smol)
			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;
		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 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 19 ms 19308 KB Output is correct
5 Correct 24 ms 19308 KB Output is correct
6 Correct 89 ms 23308 KB Output is correct
7 Correct 113 ms 20972 KB Output is correct
8 Correct 165 ms 21996 KB Output is correct
9 Correct 500 ms 26092 KB Output is correct
10 Correct 2099 ms 32332 KB Output is correct
11 Correct 1492 ms 25452 KB Output is correct
12 Correct 3055 ms 34104 KB Output is correct
13 Correct 4088 ms 27652 KB Output is correct
14 Correct 2185 ms 24548 KB Output is correct
15 Correct 2807 ms 31780 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 4980 ms 29024 KB Output isn't correct
2 Incorrect 7693 ms 26864 KB Output isn't correct
3 Execution timed out 8071 ms 34224 KB Time limit exceeded
4 Runtime error 760 ms 131076 KB Execution killed with signal 9
5 Runtime error 620 ms 131076 KB Execution killed with signal 9
6 Runtime error 648 ms 131076 KB Execution killed with signal 9
7 Runtime error 542 ms 131072 KB Execution killed with signal 9
8 Runtime error 665 ms 131076 KB Execution killed with signal 9
9 Runtime error 577 ms 131076 KB Execution killed with signal 9
10 Runtime error 601 ms 131076 KB Execution killed with signal 9
11 Runtime error 644 ms 131076 KB Execution killed with signal 9
12 Runtime error 668 ms 131076 KB Execution killed with signal 9
13 Runtime error 673 ms 131076 KB Execution killed with signal 9
14 Runtime error 693 ms 131076 KB Execution killed with signal 9
15 Runtime error 669 ms 131076 KB Execution killed with signal 9
16 Runtime error 673 ms 131076 KB Execution killed with signal 9
17 Runtime error 677 ms 131076 KB Execution killed with signal 9