Submission #945461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
945461	2024-03-13T20:25:05 Z	mc061	Regions (IOI09_regions)	C++14	95 / 100	8000 ms	125004 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 = 180;
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	4 ms	18776 KB	Output is correct
4	Correct	6 ms	18776 KB	Output is correct
5	Correct	8 ms	18776 KB	Output is correct
6	Correct	15 ms	19032 KB	Output is correct
7	Correct	22 ms	19168 KB	Output is correct
8	Correct	24 ms	19032 KB	Output is correct
9	Correct	61 ms	20008 KB	Output is correct
10	Correct	65 ms	20656 KB	Output is correct
11	Correct	145 ms	21444 KB	Output is correct
12	Correct	282 ms	22556 KB	Output is correct
13	Correct	146 ms	23040 KB	Output is correct
14	Correct	338 ms	23852 KB	Output is correct
15	Correct	968 ms	33308 KB	Output is correct

Subtask #2

80.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1027 ms	48364 KB	Output is correct
2	Correct	777 ms	48276 KB	Output is correct
3	Correct	1116 ms	61136 KB	Output is correct
4	Correct	431 ms	24608 KB	Output is correct
5	Correct	826 ms	26928 KB	Output is correct
6	Correct	419 ms	35208 KB	Output is correct
7	Correct	1309 ms	39300 KB	Output is correct
8	Correct	2587 ms	54040 KB	Output is correct
9	Correct	5603 ms	60048 KB	Output is correct
10	Correct	3203 ms	119464 KB	Output is correct
11	Correct	5335 ms	118064 KB	Output is correct
12	Correct	5697 ms	114768 KB	Output is correct
13	Correct	4596 ms	116372 KB	Output is correct
14	Correct	5001 ms	84864 KB	Output is correct
15	Correct	5024 ms	124396 KB	Output is correct
16	Correct	4153 ms	125004 KB	Output is correct
17	Execution timed out	8044 ms	99740 KB	Time limit exceeded