oj.uz

Submission #365085

# Submission time Handle Problem Language Result Execution time Memory
365085 2021-02-10T21:24:44 Z crackersamdjam Regions (IOI09_regions) C++17
14 / 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;
vector<int> adj[MM];
int in[MM], out[MM], t;
map<int, int> cnt[MM], parcnt;
int val[MM];
vector<pair<int, int>> down[MM], up[MM];
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[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
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28524 KB Output is correct
2 Correct 19 ms 28524 KB Output is correct
3 Correct 21 ms 28524 KB Output is correct
4 Correct 24 ms 28800 KB Output is correct
5 Correct 31 ms 28780 KB Output is correct
6 Correct 97 ms 32640 KB Output is correct
7 Correct 119 ms 31488 KB Output is correct
8 Correct 173 ms 32108 KB Output is correct
9 Correct 476 ms 35308 KB Output is correct
10 Correct 2092 ms 68364 KB Output is correct
11 Correct 1596 ms 43092 KB Output is correct
12 Correct 3037 ms 44260 KB Output is correct
13 Runtime error 2021 ms 131072 KB Execution killed with signal 9
14 Correct 2290 ms 74524 KB Output is correct
15 Correct 2921 ms 41236 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 5112 ms 69468 KB Output isn't correct
2 Runtime error 1898 ms 131076 KB Execution killed with signal 9
3 Execution timed out 8064 ms 48008 KB Time limit exceeded
4 Runtime error 517 ms 131076 KB Execution killed with signal 9
5 Runtime error 514 ms 131076 KB Execution killed with signal 9
6 Runtime error 558 ms 131076 KB Execution killed with signal 9
7 Runtime error 507 ms 131076 KB Execution killed with signal 9
8 Runtime error 568 ms 131072 KB Execution killed with signal 9
9 Runtime error 532 ms 131072 KB Execution killed with signal 9
10 Runtime error 582 ms 131076 KB Execution killed with signal 9
11 Runtime error 593 ms 131076 KB Execution killed with signal 9
12 Runtime error 630 ms 131076 KB Execution killed with signal 9
13 Runtime error 627 ms 131076 KB Execution killed with signal 9
14 Runtime error 652 ms 131076 KB Execution killed with signal 9
15 Runtime error 669 ms 131076 KB Execution killed with signal 9
16 Runtime error 631 ms 131076 KB Execution killed with signal 9
17 Runtime error 631 ms 131076 KB Execution killed with signal 9