oj.uz

Submission #945452

# Submission time Handle Problem Language Result Execution time Memory
945452 2024-03-13T19:53:21 Z mc061 Regions (IOI09_regions) C++17
55 / 100
 8000 ms 71852 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 = 500;
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 3 ms 18776 KB Output is correct
2 Correct 6 ms 18860 KB Output is correct
3 Correct 4 ms 18776 KB Output is correct
4 Correct 7 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 20 ms 19032 KB Output is correct
8 Correct 26 ms 19032 KB Output is correct
9 Correct 76 ms 19956 KB Output is correct
10 Correct 81 ms 20532 KB Output is correct
11 Correct 180 ms 21336 KB Output is correct
12 Correct 339 ms 22412 KB Output is correct
13 Correct 148 ms 22896 KB Output is correct
14 Correct 368 ms 23884 KB Output is correct
15 Correct 1700 ms 27508 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 6661 ms 35112 KB Output is correct
2 Correct 2713 ms 34852 KB Output is correct
3 Execution timed out 8068 ms 39384 KB Time limit exceeded
4 Correct 482 ms 24000 KB Output is correct
5 Correct 1055 ms 26340 KB Output is correct
6 Correct 2794 ms 30104 KB Output is correct
7 Correct 5535 ms 31236 KB Output is correct
8 Execution timed out 8083 ms 42292 KB Time limit exceeded
9 Execution timed out 8010 ms 46268 KB Time limit exceeded
10 Execution timed out 8036 ms 53064 KB Time limit exceeded
11 Execution timed out 8032 ms 54736 KB Time limit exceeded
12 Correct 4154 ms 52516 KB Output is correct
13 Execution timed out 8015 ms 53944 KB Time limit exceeded
14 Correct 5970 ms 56948 KB Output is correct
15 Execution timed out 8087 ms 60624 KB Time limit exceeded
16 Execution timed out 8074 ms 71852 KB Time limit exceeded
17 Execution timed out 8055 ms 71572 KB Time limit exceeded