oj.uz

Submission #365116

# Submission time Handle Problem Language Result Execution time Memory
365116 2021-02-10T22:25:30 Z crackersamdjam Regions (IOI09_regions) C++17
90 / 100
 6092 ms 115948 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 = 25000, SQ = 501;

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);
		}
	}

	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 19 ms 23788 KB Output is correct
5 Correct 25 ms 23936 KB Output is correct
6 Correct 28 ms 24044 KB Output is correct
7 Correct 35 ms 23916 KB Output is correct
8 Correct 52 ms 24044 KB Output is correct
9 Correct 68 ms 24960 KB Output is correct
10 Correct 122 ms 24556 KB Output is correct
11 Correct 184 ms 24920 KB Output is correct
12 Correct 178 ms 25836 KB Output is correct
13 Correct 243 ms 24940 KB Output is correct
14 Correct 366 ms 25708 KB Output is correct
15 Correct 355 ms 32364 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1635 ms 30860 KB Output is correct
2 Correct 1767 ms 28264 KB Output is correct
3 Correct 2872 ms 34848 KB Output is correct
4 Correct 349 ms 26092 KB Output is correct
5 Correct 475 ms 30060 KB Output is correct
6 Correct 1824 ms 28140 KB Output is correct
7 Correct 2103 ms 29096 KB Output is correct
8 Correct 1731 ms 40940 KB Output is correct
9 Correct 3031 ms 36724 KB Output is correct
10 Correct 5654 ms 49408 KB Output is correct
11 Correct 6092 ms 35564 KB Output is correct
12 Correct 1878 ms 67692 KB Output is correct
13 Correct 2742 ms 69140 KB Output is correct
14 Correct 3173 ms 78240 KB Output is correct
15 Incorrect 3834 ms 97900 KB Output isn't correct
16 Incorrect 3915 ms 115948 KB Output isn't correct
17 Correct 3538 ms 103020 KB Output is correct