oj.uz

Submission #365110

# Submission time Handle Problem Language Result Execution time Memory
365110 2021-02-10T22:04:07 Z crackersamdjam Regions (IOI09_regions) C++17
90 / 100
 7629 ms 111212 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

using namespace std;
const int MM = 2e5+5, NN = 25000, 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][NN];
int ans2[NN][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]][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 22 ms 19180 KB Output is correct
4 Correct 27 ms 19180 KB Output is correct
5 Correct 21 ms 19180 KB Output is correct
6 Correct 34 ms 19456 KB Output is correct
7 Correct 51 ms 19308 KB Output is correct
8 Correct 69 ms 19308 KB Output is correct
9 Correct 72 ms 20204 KB Output is correct
10 Correct 124 ms 19820 KB Output is correct
11 Correct 208 ms 20204 KB Output is correct
12 Correct 260 ms 21100 KB Output is correct
13 Correct 295 ms 20204 KB Output is correct
14 Correct 599 ms 20972 KB Output is correct
15 Correct 515 ms 27628 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1761 ms 26044 KB Output is correct
2 Correct 2048 ms 23532 KB Output is correct
3 Correct 3824 ms 29924 KB Output is correct
4 Correct 434 ms 21484 KB Output is correct
5 Correct 498 ms 25452 KB Output is correct
6 Correct 1823 ms 23532 KB Output is correct
7 Correct 2915 ms 24748 KB Output is correct
8 Correct 2877 ms 36300 KB Output is correct
9 Correct 4673 ms 32108 KB Output is correct
10 Correct 7388 ms 45180 KB Output is correct
11 Correct 7629 ms 31404 KB Output is correct
12 Correct 2195 ms 63176 KB Output is correct
13 Correct 3338 ms 64368 KB Output is correct
14 Correct 3247 ms 73596 KB Output is correct
15 Incorrect 5241 ms 93268 KB Output isn't correct
16 Incorrect 5894 ms 111212 KB Output isn't correct
17 Correct 5048 ms 98008 KB Output is correct