oj.uz

Submission #365118

# Submission time Handle Problem Language Result Execution time Memory
365118 2021-02-10T22:28:18 Z crackersamdjam Regions (IOI09_regions) C++17
100 / 100
 6767 ms 110828 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, NN = 25001, SQ = 450;

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

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

void dfs(int cur, int pre){
	in[cur] = ++t;
	pos[val[cur]].emplace_back(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]];

	if(!--parcnt[val[cur]]){
		parcnt.erase(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);
		}
		pos[i].reserve(size(nodes[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{
			int ret = 0;
			for(int j: nodes[a]){
				ret += upper_bound(all(pos[b]), out[j]) - lower_bound(all(pos[b]), in[j]);
			}
			cout<<ret<<'\n';
		}
		cout<<flush;
	}
}
/*
precompute big-small, small-small, small-big
brute force small-small
*/

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 18 ms 23788 KB Output is correct
4 Correct 20 ms 23788 KB Output is correct
5 Correct 24 ms 23916 KB Output is correct
6 Correct 41 ms 24192 KB Output is correct
7 Correct 36 ms 23916 KB Output is correct
8 Correct 56 ms 24044 KB Output is correct
9 Correct 65 ms 24812 KB Output is correct
10 Correct 127 ms 24556 KB Output is correct
11 Correct 161 ms 24812 KB Output is correct
12 Correct 143 ms 25856 KB Output is correct
13 Correct 262 ms 24812 KB Output is correct
14 Correct 421 ms 25580 KB Output is correct
15 Correct 509 ms 32236 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1623 ms 30712 KB Output is correct
2 Correct 1661 ms 28012 KB Output is correct
3 Correct 2903 ms 34640 KB Output is correct
4 Correct 349 ms 26092 KB Output is correct
5 Correct 402 ms 30136 KB Output is correct
6 Correct 838 ms 42688 KB Output is correct
7 Correct 2228 ms 47356 KB Output is correct
8 Correct 1852 ms 62956 KB Output is correct
9 Correct 3241 ms 36516 KB Output is correct
10 Correct 4793 ms 98668 KB Output is correct
11 Correct 6767 ms 35292 KB Output is correct
12 Correct 1986 ms 64664 KB Output is correct
13 Correct 2725 ms 65936 KB Output is correct
14 Correct 2818 ms 74220 KB Output is correct
15 Correct 4239 ms 92616 KB Output is correct
16 Correct 3625 ms 110828 KB Output is correct
17 Correct 3644 ms 99116 KB Output is correct