Submission #945460

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
945460	2024-03-13T20:22:54 Z	mc061	Regions (IOI09_regions)	C++14	90 / 100	8000 ms	124616 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 = 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<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	4 ms	18776 KB	Output is correct
4	Correct	6 ms	18776 KB	Output is correct
5	Correct	7 ms	18776 KB	Output is correct
6	Correct	13 ms	19032 KB	Output is correct
7	Correct	18 ms	19172 KB	Output is correct
8	Correct	23 ms	19032 KB	Output is correct
9	Correct	59 ms	19984 KB	Output is correct
10	Correct	62 ms	20632 KB	Output is correct
11	Correct	155 ms	21440 KB	Output is correct
12	Correct	269 ms	22552 KB	Output is correct
13	Correct	161 ms	23052 KB	Output is correct
14	Correct	310 ms	23856 KB	Output is correct
15	Correct	1105 ms	29204 KB	Output is correct

Subtask #2

75.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2201 ms	42204 KB	Output is correct
2	Correct	768 ms	48024 KB	Output is correct
3	Correct	1112 ms	61436 KB	Output is correct
4	Correct	446 ms	24604 KB	Output is correct
5	Correct	814 ms	26928 KB	Output is correct
6	Correct	469 ms	35416 KB	Output is correct
7	Correct	1479 ms	39516 KB	Output is correct
8	Correct	2684 ms	54456 KB	Output is correct
9	Correct	5571 ms	59856 KB	Output is correct
10	Correct	7291 ms	96752 KB	Output is correct
11	Correct	5007 ms	117812 KB	Output is correct
12	Correct	4189 ms	85932 KB	Output is correct
13	Correct	5293 ms	87092 KB	Output is correct
14	Correct	5138 ms	61844 KB	Output is correct
15	Execution timed out	8013 ms	64056 KB	Time limit exceeded
16	Correct	4169 ms	124616 KB	Output is correct
17	Execution timed out	8060 ms	76644 KB	Time limit exceeded