oj.uz

Submission #365119

# Submission time Handle Problem Language Result Execution time Memory
365119 2021-02-10T22:48:13 Z crackersamdjam Regions (IOI09_regions) C++17
100 / 100
 5798 ms 85740 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;
constexpr int MM = 2e5+1, NN = 25001, SQ = 450;

int n, m, q;
int val[MM];
vector<int> adj[MM];
int in[MM], out[MM], t;
vector<int> nodes[MM], pos[MM];
int bid[MM];
vector<int> big;

int parcnt[NN], sub[MM];

int ans1[SQ][NN];
int ans2[NN][SQ];

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]]++;

	for(auto u: adj[cur]){
		if(u != pre)
			dfs(u, cur);
	}

	parcnt[val[cur]]--;
	out[cur] = t;
}

void go(int cur, int pre, int col){
	sub[cur] = val[cur] == col;
	for(auto u: adj[cur]){
		if(u != pre){
			go(u, cur, col);
			sub[cur] += sub[u];
		}
	}
	//do small to big and big to big
	ans2[val[cur]][bid[col]] += sub[cur];
	// pr("two", val[cur], col, sub[cur], ans2[val[cur]][bid[col]]);
}

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; i < size(big); i++){
		go(1, 0, big[i]);
	}

	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]) - upper_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: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: In function 'int main()':
regions.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i = 0; i < size(big); i++){
      |                 ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 13 ms 14444 KB Output is correct
4 Correct 14 ms 14444 KB Output is correct
5 Correct 15 ms 14444 KB Output is correct
6 Correct 32 ms 14572 KB Output is correct
7 Correct 50 ms 14572 KB Output is correct
8 Correct 45 ms 14572 KB Output is correct
9 Correct 73 ms 15084 KB Output is correct
10 Correct 100 ms 14956 KB Output is correct
11 Correct 149 ms 15212 KB Output is correct
12 Correct 187 ms 15852 KB Output is correct
13 Correct 277 ms 15340 KB Output is correct
14 Correct 312 ms 15980 KB Output is correct
15 Correct 323 ms 19692 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1338 ms 20204 KB Output is correct
2 Correct 1676 ms 18540 KB Output is correct
3 Correct 2954 ms 22764 KB Output is correct
4 Correct 347 ms 16108 KB Output is correct
5 Correct 442 ms 18412 KB Output is correct
6 Correct 1014 ms 31852 KB Output is correct
7 Correct 2033 ms 36972 KB Output is correct
8 Correct 1402 ms 47980 KB Output is correct
9 Correct 2961 ms 24300 KB Output is correct
10 Correct 4349 ms 81644 KB Output is correct
11 Correct 5798 ms 23660 KB Output is correct
12 Correct 1837 ms 53868 KB Output is correct
13 Correct 2612 ms 54508 KB Output is correct
14 Correct 2802 ms 62700 KB Output is correct
15 Correct 4024 ms 76524 KB Output is correct
16 Correct 3558 ms 85740 KB Output is correct
17 Correct 3653 ms 76140 KB Output is correct