oj.uz

Submission #945448

# Submission time Handle Problem Language Result Execution time Memory
945448 2024-03-13T19:41:12 Z mc061 Regions (IOI09_regions) C++17
40 / 100
 8000 ms 131072 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 + 3;
const int R = 25000;
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) {
	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][R] = {};
vector<int> comp[R];
int bigindex[N / BLOCK];

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:33:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  while (p1 < v1.size() && p2 < v2.size()) {
      |         ~~~^~~~~~~~~~~
regions.cpp:33:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  while (p1 < v1.size() && p2 < v2.size()) {
      |                           ~~~^~~~~~~~~~~
regions.cpp:37:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  while (p1 < v1.size()) dest.push_back(v1[p1++]);
      |         ~~~^~~~~~~~~~~
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 (p2 < v2.size()) dest.push_back(v2[p2++]);
      |         ~~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 5 ms 19032 KB Output is correct
3 Correct 4 ms 19032 KB Output is correct
4 Correct 5 ms 19032 KB Output is correct
5 Correct 8 ms 19284 KB Output is correct
6 Correct 15 ms 19032 KB Output is correct
7 Correct 19 ms 19288 KB Output is correct
8 Correct 30 ms 19288 KB Output is correct
9 Correct 65 ms 20064 KB Output is correct
10 Correct 78 ms 20628 KB Output is correct
11 Correct 178 ms 21384 KB Output is correct
12 Correct 343 ms 22424 KB Output is correct
13 Correct 144 ms 22860 KB Output is correct
14 Correct 363 ms 23800 KB Output is correct
15 Correct 1698 ms 27356 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 7031 ms 32944 KB Output is correct
2 Correct 2785 ms 32468 KB Output is correct
3 Execution timed out 8034 ms 36944 KB Time limit exceeded
4 Correct 504 ms 23928 KB Output is correct
5 Correct 1108 ms 26212 KB Output is correct
6 Runtime error 265 ms 60056 KB Execution killed with signal 11
7 Correct 5649 ms 30936 KB Output is correct
8 Runtime error 3220 ms 84848 KB Execution killed with signal 11
9 Execution timed out 8007 ms 45548 KB Time limit exceeded
10 Execution timed out 8041 ms 52508 KB Time limit exceeded
11 Execution timed out 8077 ms 53704 KB Time limit exceeded
12 Runtime error 4301 ms 104364 KB Execution killed with signal 11
13 Execution timed out 8066 ms 52940 KB Time limit exceeded
14 Runtime error 514 ms 113064 KB Execution killed with signal 11
15 Runtime error 4209 ms 120896 KB Execution killed with signal 11
16 Execution timed out 8057 ms 70852 KB Time limit exceeded
17 Runtime error 2591 ms 131072 KB Execution killed with signal 9