oj.uz

답안 #945451

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945451 2024-03-13T19:48:04 Z mc061 Regions (IOI09_regions) C++17
35 / 100
 8000 ms 131076 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 = 300;
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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 4 ms 19032 KB Output is correct
3 Correct 6 ms 19032 KB Output is correct
4 Correct 5 ms 19032 KB Output is correct
5 Correct 7 ms 19032 KB Output is correct
6 Correct 14 ms 19032 KB Output is correct
7 Correct 21 ms 19288 KB Output is correct
8 Correct 25 ms 19288 KB Output is correct
9 Correct 70 ms 20124 KB Output is correct
10 Correct 66 ms 20704 KB Output is correct
11 Correct 183 ms 21504 KB Output is correct
12 Correct 357 ms 22588 KB Output is correct
13 Correct 169 ms 23060 KB Output is correct
14 Correct 408 ms 24044 KB Output is correct
15 Correct 1784 ms 27684 KB Output is correct

Subtask #2
20.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6064 ms 35524 KB Output is correct
2 Correct 2787 ms 32984 KB Output is correct
3 Execution timed out 8064 ms 37632 KB Time limit exceeded
4 Correct 470 ms 24176 KB Output is correct
5 Correct 1044 ms 26512 KB Output is correct
6 Runtime error 167 ms 69176 KB Execution killed with signal 11
7 Runtime error 244 ms 72080 KB Execution killed with signal 11
8 Runtime error 254 ms 102816 KB Execution killed with signal 11
9 Runtime error 776 ms 104444 KB Execution killed with signal 11
10 Runtime error 2881 ms 131072 KB Execution killed with signal 9
11 Runtime error 1039 ms 128308 KB Execution killed with signal 11
12 Incorrect 4136 ms 53008 KB Output isn't correct
13 Incorrect 7939 ms 54524 KB Output isn't correct
14 Runtime error 859 ms 116012 KB Execution killed with signal 11
15 Execution timed out 8036 ms 61060 KB Time limit exceeded
16 Execution timed out 8082 ms 72272 KB Time limit exceeded
17 Runtime error 4444 ms 131076 KB Execution killed with signal 9