oj.uz

Submission #945447

# Submission time Handle Problem Language Result Execution time Memory
945447 2024-03-13T19:39:26 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 = 200;
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 4 ms 19032 KB Output is correct
3 Correct 5 ms 19032 KB Output is correct
4 Correct 8 ms 19032 KB Output is correct
5 Correct 8 ms 19032 KB Output is correct
6 Correct 16 ms 19256 KB Output is correct
7 Correct 21 ms 19288 KB Output is correct
8 Correct 24 ms 19288 KB Output is correct
9 Correct 75 ms 20116 KB Output is correct
10 Correct 72 ms 20700 KB Output is correct
11 Correct 181 ms 21520 KB Output is correct
12 Correct 348 ms 22592 KB Output is correct
13 Correct 143 ms 23076 KB Output is correct
14 Correct 380 ms 24044 KB Output is correct
15 Correct 1682 ms 29552 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3120 ms 41432 KB Output is correct
2 Correct 771 ms 47348 KB Output is correct
3 Correct 1110 ms 62252 KB Output is correct
4 Correct 475 ms 24164 KB Output is correct
5 Correct 1083 ms 26516 KB Output is correct
6 Runtime error 233 ms 69176 KB Execution killed with signal 11
7 Runtime error 207 ms 76488 KB Execution killed with signal 11
8 Runtime error 472 ms 102860 KB Execution killed with signal 11
9 Runtime error 3347 ms 112400 KB Execution killed with signal 11
10 Runtime error 3510 ms 131072 KB Execution killed with signal 9
11 Runtime error 6210 ms 131072 KB Execution killed with signal 9
12 Runtime error 4910 ms 131072 KB Execution killed with signal 9
13 Runtime error 4452 ms 131072 KB Execution killed with signal 9
14 Runtime error 630 ms 115604 KB Execution killed with signal 11
15 Execution timed out 8013 ms 60888 KB Time limit exceeded
16 Runtime error 3016 ms 131072 KB Execution killed with signal 9
17 Runtime error 6341 ms 131072 KB Execution killed with signal 9