oj.uz

Submission #365109

# Submission time Handle Problem Language Result Execution time Memory
365109 2021-02-10T22:02:42 Z crackersamdjam Regions (IOI09_regions) C++17
55 / 100
 7560 ms 111340 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

using namespace std;
const int MM = 2e5+5, NN = 25000, SQ = 500;

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]][bid[i]] += cnt[cur][big[i]];

	parcnt[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{
			for(int j: nodes[b])
				update(in[j], 1);
			
			int ret = 0;
			for(int j: nodes[a])
				ret += query(out[j]) - query(in[j]-1);
			
			for(int j: nodes[b])
				update(in[j], -1);

			cout<<ret<<'\n';
		}
	}
}
/*
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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19180 KB Output is correct
2 Correct 18 ms 19180 KB Output is correct
3 Correct 16 ms 19180 KB Output is correct
4 Correct 28 ms 19180 KB Output is correct
5 Correct 29 ms 19180 KB Output is correct
6 Correct 33 ms 19308 KB Output is correct
7 Correct 53 ms 19440 KB Output is correct
8 Correct 51 ms 19308 KB Output is correct
9 Correct 69 ms 20204 KB Output is correct
10 Correct 87 ms 19908 KB Output is correct
11 Correct 234 ms 20204 KB Output is correct
12 Correct 204 ms 21100 KB Output is correct
13 Correct 283 ms 20204 KB Output is correct
14 Correct 403 ms 20972 KB Output is correct
15 Correct 538 ms 27652 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1915 ms 26044 KB Output isn't correct
2 Incorrect 2268 ms 23492 KB Output isn't correct
3 Incorrect 4170 ms 30208 KB Output isn't correct
4 Correct 457 ms 21484 KB Output is correct
5 Correct 444 ms 25452 KB Output is correct
6 Correct 2098 ms 23532 KB Output is correct
7 Correct 2673 ms 24748 KB Output is correct
8 Correct 3104 ms 36332 KB Output is correct
9 Correct 4381 ms 31980 KB Output is correct
10 Correct 7419 ms 45036 KB Output is correct
11 Correct 7560 ms 31184 KB Output is correct
12 Incorrect 2313 ms 63340 KB Output isn't correct
13 Incorrect 3214 ms 64600 KB Output isn't correct
14 Incorrect 3390 ms 73648 KB Output isn't correct
15 Incorrect 5276 ms 93268 KB Output isn't correct
16 Incorrect 5403 ms 111340 KB Output isn't correct
17 Incorrect 5554 ms 98028 KB Output isn't correct