Submission #945462

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
945462	2024-03-13T20:27:04 Z	mc061	Regions (IOI09_regions)	C++14	100 / 100	5437 ms	124472 KB

regions

#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<pair<int, int>> seg[2 * N];
int get_node_count(const vector<pair<int, int>>& node, const int& element) {
	auto it = lower_bound(node.begin(), node.end(), make_pair(element, -1));
	if (it == node.end() || it->first != element) return 0;
	return it->second;
}
void combine(vector<pair<int, int>>& dest, const vector<pair<int, int>>& v1, const vector<pair<int, int>>& v2) {
	int p1 = 0, p2 = 0;
	while (p1 < v1.size() && p2 < v2.size()) {
		if (v1[p1].first < v2[p2].first) dest.push_back(v1[p1++]);
		else if (v2[p2].first < v1[p1].first) dest.push_back(v2[p2++]);
		else if (v1[p1].first == v2[p2].first) dest.emplace_back(v1[p1].first, v1[p1].second + v2[p2].second), ++p1, ++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]], 1});
	}
	for (int i = n - 1; i > 0; --i) {
		combine(seg[i], seg[i << 1], seg[i << 1 | 1]);
	}
}

const int BLOCK = 160;
int cnt[N / BLOCK][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<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&)':
regions.cpp:35:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  while (p1 < v1.size() && p2 < v2.size()) {
      |         ~~~^~~~~~~~~~~
regions.cpp:35:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  while (p1 < v1.size() && p2 < v2.size()) {
      |                           ~~~^~~~~~~~~~~
regions.cpp:40:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  while (p1 < v1.size()) dest.push_back(v1[p1++]);
      |         ~~~^~~~~~~~~~~
regions.cpp:41:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  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	18776 KB	Output is correct
2	Correct	4 ms	18776 KB	Output is correct
3	Correct	5 ms	18776 KB	Output is correct
4	Correct	5 ms	18776 KB	Output is correct
5	Correct	8 ms	18776 KB	Output is correct
6	Correct	13 ms	19032 KB	Output is correct
7	Correct	18 ms	19168 KB	Output is correct
8	Correct	22 ms	19032 KB	Output is correct
9	Correct	56 ms	19988 KB	Output is correct
10	Correct	82 ms	20596 KB	Output is correct
11	Correct	154 ms	21376 KB	Output is correct
12	Correct	280 ms	22476 KB	Output is correct
13	Correct	151 ms	22944 KB	Output is correct
14	Correct	296 ms	27844 KB	Output is correct
15	Correct	451 ms	45460 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	727 ms	52176 KB	Output is correct
2	Correct	786 ms	47712 KB	Output is correct
3	Correct	1031 ms	60780 KB	Output is correct
4	Correct	366 ms	26640 KB	Output is correct
5	Correct	810 ms	26780 KB	Output is correct
6	Correct	451 ms	34996 KB	Output is correct
7	Correct	1208 ms	41076 KB	Output is correct
8	Correct	2793 ms	53660 KB	Output is correct
9	Correct	5437 ms	61528 KB	Output is correct
10	Correct	3185 ms	118816 KB	Output is correct
11	Correct	4640 ms	117244 KB	Output is correct
12	Correct	4962 ms	114044 KB	Output is correct
13	Correct	4541 ms	115752 KB	Output is correct
14	Correct	5284 ms	108712 KB	Output is correct
15	Correct	4979 ms	123992 KB	Output is correct
16	Correct	3914 ms	124472 KB	Output is correct
17	Correct	4032 ms	123428 KB	Output is correct