oj.uz

Submission #365115

# Submission time Handle Problem Language Result Execution time Memory
365115 2021-02-10T22:18:59 Z crackersamdjam Regions (IOI09_regions) C++17
3 / 100
 4550 ms 109848 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

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

	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 = 1; i <= m; i++){
		for(int &j: nodes[i])
			j = in[j];
	}


	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(nodes[b]), out[j]) - lower_bound(all(nodes[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: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
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 19180 KB Output isn't correct
2 Incorrect 13 ms 19180 KB Output isn't correct
3 Incorrect 15 ms 19180 KB Output isn't correct
4 Incorrect 17 ms 19196 KB Output isn't correct
5 Incorrect 20 ms 19180 KB Output isn't correct
6 Correct 32 ms 19308 KB Output is correct
7 Incorrect 35 ms 19180 KB Output isn't correct
8 Incorrect 45 ms 19308 KB Output isn't correct
9 Correct 63 ms 20204 KB Output is correct
10 Incorrect 104 ms 19820 KB Output isn't correct
11 Incorrect 142 ms 20076 KB Output isn't correct
12 Incorrect 163 ms 20972 KB Output isn't correct
13 Incorrect 212 ms 20076 KB Output isn't correct
14 Incorrect 314 ms 20844 KB Output isn't correct
15 Correct 323 ms 27372 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1268 ms 25720 KB Output isn't correct
2 Incorrect 1322 ms 23160 KB Output isn't correct
3 Incorrect 2436 ms 29712 KB Output isn't correct
4 Incorrect 369 ms 21228 KB Output isn't correct
5 Incorrect 307 ms 25228 KB Output isn't correct
6 Incorrect 1108 ms 23276 KB Output isn't correct
7 Incorrect 1525 ms 24044 KB Output isn't correct
8 Incorrect 1629 ms 35564 KB Output isn't correct
9 Incorrect 2520 ms 30956 KB Output isn't correct
10 Incorrect 4550 ms 43372 KB Output isn't correct
11 Incorrect 4040 ms 29420 KB Output isn't correct
12 Incorrect 1640 ms 61932 KB Output isn't correct
13 Incorrect 1770 ms 63172 KB Output isn't correct
14 Incorrect 2893 ms 72300 KB Output isn't correct
15 Incorrect 3314 ms 91508 KB Output isn't correct
16 Incorrect 3445 ms 109848 KB Output isn't correct
17 Incorrect 3818 ms 96932 KB Output isn't correct