oj.uz

Submission #365108

# Submission time Handle Problem Language Result Execution time Memory
365108 2021-02-10T22:01:34 Z crackersamdjam Regions (IOI09_regions) C++17
55 / 100
 7859 ms 111172 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

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], bid[MM];
vector<int> big;

int ans1[SQ][MM];
int ans2[MM][SQ]; //swap order if still not fast enough

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){
		//do big to small only
		for(int i = 0; i < size(big); i++)
			ans1[i][val[cur]] += parcnt[big[i]];
	}
	parcnt[val[cur]]++;

	int id = 0;
	for(auto u: adj[cur]){
		if(u != pre){
			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 and u != id){
			for(auto [a, c]: cnt[u]){
				cnt[cur][a] += c;
			}
			cnt[u].clear();
		}
	}
	cnt[cur][val[cur]]++;

	//do small to big and big to big
	for(int i = 0; i < size(big); i++)
		ans2[val[cur]][bid[i]] += cnt[cur][big[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){
			bid[i] = size(big);
			big.emplace_back(i);
		}
	}

	dfs(1, 0);

	for(int i = 0,a,b; i < q; i++){
		cin>>a>>b;
		if(size(nodes[b]) > SQ){
			cout<<ans2[a][bid[b]]<<'\n';
		}
		else if(size(nodes[a]) > SQ){
			cout<<ans1[bid[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';
		}
	}
}
/*
precompute big-small, small-small, small-big
brute force small-small
*/

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i = 0; i < size(big); i++)
      |                  ~~^~~~~~~~~~~
regions.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i = 0; i < size(big); i++)
      |                 ~~^~~~~~~~~~~

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 19 ms 19180 KB Output is correct
5 Correct 20 ms 19180 KB Output is correct
6 Correct 28 ms 19308 KB Output is correct
7 Correct 41 ms 19308 KB Output is correct
8 Correct 61 ms 19308 KB Output is correct
9 Correct 86 ms 20204 KB Output is correct
10 Correct 109 ms 19820 KB Output is correct
11 Correct 142 ms 20204 KB Output is correct
12 Correct 187 ms 21120 KB Output is correct
13 Correct 299 ms 20204 KB Output is correct
14 Correct 459 ms 20972 KB Output is correct
15 Correct 496 ms 27628 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1753 ms 26040 KB Output isn't correct
2 Incorrect 1968 ms 23500 KB Output isn't correct
3 Incorrect 3650 ms 30060 KB Output isn't correct
4 Correct 504 ms 21484 KB Output is correct
5 Correct 525 ms 25528 KB Output is correct
6 Correct 1953 ms 23572 KB Output is correct
7 Correct 2766 ms 24684 KB Output is correct
8 Correct 2599 ms 36332 KB Output is correct
9 Correct 4745 ms 32008 KB Output is correct
10 Correct 7559 ms 45036 KB Output is correct
11 Correct 7859 ms 31052 KB Output is correct
12 Incorrect 2318 ms 63596 KB Output isn't correct
13 Incorrect 3659 ms 64364 KB Output isn't correct
14 Incorrect 4310 ms 73632 KB Output isn't correct
15 Incorrect 6222 ms 93204 KB Output isn't correct
16 Incorrect 6826 ms 111172 KB Output isn't correct
17 Incorrect 5811 ms 98136 KB Output isn't correct