oj.uz

Submission #365117

# Submission time Handle Problem Language Result Execution time Memory
365117 2021-02-10T22:27:42 Z crackersamdjam Regions (IOI09_regions) C++17
90 / 100
 6834 ms 110832 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 = 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 19 ms 23788 KB Output is correct
4 Correct 20 ms 23788 KB Output is correct
5 Correct 26 ms 24044 KB Output is correct
6 Correct 40 ms 24044 KB Output is correct
7 Correct 47 ms 23916 KB Output is correct
8 Correct 57 ms 24044 KB Output is correct
9 Correct 65 ms 24940 KB Output is correct
10 Correct 109 ms 24556 KB Output is correct
11 Correct 154 ms 24812 KB Output is correct
12 Correct 181 ms 25708 KB Output is correct
13 Correct 236 ms 24940 KB Output is correct
14 Correct 355 ms 25580 KB Output is correct
15 Correct 324 ms 32236 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1487 ms 30712 KB Output is correct
2 Correct 1840 ms 28140 KB Output is correct
3 Correct 3096 ms 34668 KB Output is correct
4 Correct 401 ms 26092 KB Output is correct
5 Correct 541 ms 30060 KB Output is correct
6 Correct 970 ms 42604 KB Output is correct
7 Correct 2023 ms 47340 KB Output is correct
8 Correct 1648 ms 63084 KB Output is correct
9 Correct 2841 ms 36468 KB Output is correct
10 Correct 4399 ms 98724 KB Output is correct
11 Correct 6834 ms 35308 KB Output is correct
12 Correct 2029 ms 64620 KB Output is correct
13 Correct 3057 ms 65764 KB Output is correct
14 Correct 3106 ms 74216 KB Output is correct
15 Incorrect 4274 ms 92576 KB Output isn't correct
16 Incorrect 4452 ms 110832 KB Output isn't correct
17 Correct 4083 ms 99052 KB Output is correct