oj.uz

Submission #945453

# Submission time Handle Problem Language Result Execution time Memory
945453 2024-03-13T19:56:07 Z mc061 Regions (IOI09_regions) C++14
85 / 100
 8000 ms 120736 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
    #include "debug.h"
#else
	#pragma GCC optimize("O3")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    #define dbg(...) 42
    template<typename T>ostream&operator<<(ostream&os,vector<T>&vec){for(signed i=0;i+1<vec.size();++i){os<<vec[i]<<" ";}if(vec.size()>0)os<<vec.back();return os;}
#endif

const int N = 2e5 + 6;
const int R = 25001;
int n;

int col[N];
int tin[N], tout[N];
vector<int> tree[N], tour;
void build_tour(int v, int p=-1) {
	tour.push_back(v);
	tin[v] = tour.size() - 1;
	for (int u : tree[v]) if (u != p) {
		build_tour(u, v);
	}
	tout[v] = tour.size() - 1;
}
vector<int> seg[2 * N];
int get_node_count(const vector<int>& node, const int element) {
	if (!node.size()) return 0;
	return upper_bound(node.begin(), node.end(), element) - lower_bound(node.begin(), node.end(), element);
}
void combine(vector<int>& dest, const vector<int>& v1, const vector<int>& v2) {
	int p1 = 0, p2 = 0;
	while (p1 < v1.size() && p2 < v2.size()) {
		if (v1[p1] <= v2[p2]) dest.push_back(v1[p1++]);
		else dest.push_back(v2[p2++]);
	}
	while (p1 < v1.size()) dest.push_back(v1[p1++]);
	while (p2 < v2.size()) dest.push_back(v2[p2++]);
}
void build() {
	for (int i = 0; i < n; ++i) {
		seg[n + i].push_back(col[tour[i]]);
	}
	for (int i = n - 1; i > 0; --i) {
		combine(seg[i], seg[i << 1], seg[i << 1 | 1]);
	}
}

const int BLOCK = 200;
int cnt[N / BLOCK + 3][R] = {};
vector<int> comp[R];
int bigindex[N] = {};

signed main(void) {
    cin.tie(0)->sync_with_stdio(false);

	int r, q;
	cin >> n >> r >> q;
	cin >> col[1];
	--col[1];
	comp[col[1]].push_back(1);
	for (int i = 2; i <= n; ++i) {
		int p;
		cin >> p >> col[i];
		--col[i];
		comp[col[i]].push_back(i);
		tree[p].push_back(i);
		tree[i].push_back(p);
	}
	build_tour(1);
	build();
	int index = 0;
	for (int i = 0; i < r; ++i) {
		if (comp[i].size() >= BLOCK) {
			int cnt_now = 0;
			bigindex[i] = index;
			function<void(int, int)> dfs = [&] (int v, int p) -> void {
				if (col[v] == i) ++cnt_now;
				else cnt[index][col[v]] += cnt_now;
				for (int u : tree[v]) if (u != p) {
					dfs(u, v);
				}	
				if (col[v] == i) --cnt_now;
			};
			dfs(1, 1);
			++index;
		}
	}
	while (q--) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		if (comp[a].size() >= BLOCK) {
			cout << cnt[bigindex[a]][b] << endl;
			continue;
		}
		int ans = 0;
		for (int v : comp[a]) {
			int tl = tin[v] + n, tr = tout[v] + n + 1;
			for (; tl < tr; tl >>= 1, tr >>= 1) {
				if (tl&1) ans += get_node_count(seg[tl], b), ++tl;
				if (tr&1) --tr, ans += get_node_count(seg[tr], b);
			}
		}
		cout << ans << endl;
	}
}

Compilation message

regions.cpp: In function 'void combine(std::vector<int>&, const std::vector<int>&, const std::vector<int>&)':
regions.cpp:34:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  while (p1 < v1.size() && p2 < v2.size()) {
      |         ~~~^~~~~~~~~~~
regions.cpp:34:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  while (p1 < v1.size() && p2 < v2.size()) {
      |                           ~~~^~~~~~~~~~~
regions.cpp:38:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  while (p1 < v1.size()) dest.push_back(v1[p1++]);
      |         ~~~^~~~~~~~~~~
regions.cpp:39:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  while (p2 < v2.size()) dest.push_back(v2[p2++]);
      |         ~~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18772 KB Output is correct
2 Correct 4 ms 19028 KB Output is correct
3 Correct 4 ms 18776 KB Output is correct
4 Correct 5 ms 18776 KB Output is correct
5 Correct 10 ms 18776 KB Output is correct
6 Correct 20 ms 19028 KB Output is correct
7 Correct 23 ms 19032 KB Output is correct
8 Correct 28 ms 19032 KB Output is correct
9 Correct 74 ms 19920 KB Output is correct
10 Correct 68 ms 20492 KB Output is correct
11 Correct 179 ms 21280 KB Output is correct
12 Correct 338 ms 22332 KB Output is correct
13 Correct 145 ms 22792 KB Output is correct
14 Correct 350 ms 23756 KB Output is correct
15 Correct 1659 ms 29228 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3068 ms 43020 KB Output is correct
2 Correct 746 ms 48900 KB Output is correct
3 Correct 1040 ms 61724 KB Output is correct
4 Correct 506 ms 23872 KB Output is correct
5 Correct 1039 ms 26196 KB Output is correct
6 Correct 499 ms 34012 KB Output is correct
7 Correct 1755 ms 37380 KB Output is correct
8 Correct 3317 ms 52424 KB Output is correct
9 Correct 6536 ms 57008 KB Output is correct
10 Execution timed out 8082 ms 93832 KB Time limit exceeded
11 Correct 5101 ms 113632 KB Output is correct
12 Correct 4428 ms 82596 KB Output is correct
13 Correct 6353 ms 84252 KB Output is correct
14 Correct 5973 ms 58204 KB Output is correct
15 Execution timed out 8025 ms 59948 KB Time limit exceeded
16 Correct 4070 ms 120736 KB Output is correct
17 Execution timed out 8036 ms 72928 KB Time limit exceeded