oj.uz

Submission #895431

# Submission time Handle Problem Language Result Execution time Memory
895431 2023-12-29T23:58:59 Z MinaRagy06 Regions (IOI09_regions) C++17
100 / 100
 3084 ms 49336 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 200'005, inf = 1e9 + 5;
vector<int> adj[N];
int a[N], p[N], sz[N], order[N], idx[N];
vector<int> above[N], below[N], gud[N];
void calc1(int i, int c, int r) {
	above[r][a[i]] += c;
	above[r][a[i]] = min(above[r][a[i]], inf);
	c += a[i] == order[r];
	for (auto nxt : adj[i]) {
		calc1(nxt, c, r);
	}
}
int calc2(int i, int r) {
	int c = 0;
	for (auto nxt : adj[i]) {
		c += calc2(nxt, r);
	}
	below[r][a[i]] += c;
	below[r][a[i]] = min(below[r][a[i]], inf);
	return c + (a[i] == order[r]);
}
int st[N], en[N], t;
void dfs(int i) {
	st[i] = t++;
	for (auto nxt : adj[i]) {
		dfs(nxt);
	}
	en[i] = t - 1;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	memset(idx, -1, sizeof idx);
	int n, r, q;
	cin >> n >> r >> q;
	cin >> a[0];
	a[0]--;
	for (int i = 1; i < n; i++) {
		cin >> p[i] >> a[i];
		p[i]--;
		a[i]--;
		adj[p[i]].push_back(i);
	}
	for (int i = 0; i < n; i++) {
		sz[a[i]]++;
		gud[a[i]].push_back(i);
	}
	for (int i = 0; i < r; i++) {
		order[i] = i;
	}
	sort(order, order + r, [&](int x, int y) {
		return sz[x] > sz[y];
			});
	int cnt = (1 << 20) / r;
	for (int i = 0; i < min(r, cnt); i++) {
		idx[order[i]] = i;
		above[i].resize(r);
		below[i].resize(r);
		calc1(0, 0, i);
		calc2(0, i);
	}
	dfs(0);
	for (int i = 0; i < r; i++) {
		sort(gud[i].begin(), gud[i].end(), [&] (int x, int y) {
			return st[x] < st[y];
				});
	}
	while (q--) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--, r2--;
		if (~idx[r1]) {
			cout << above[idx[r1]][r2] << endl;
		} else if (~idx[r2]) {
			cout << below[idx[r2]][r1] << endl;
		} else {
			int m = gud[r2].size();
			int bit[m]{};
			auto upd = [&] (int x, int v) {
				for (int i = x; i < m; i = (i | (i + 1))) {
					bit[i] += v;
				}
			};
			auto get = [&] (int x) {
				int ret = 0;
				for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
					ret += bit[i];
				}
				return ret;
			};
			vector<int> cur = gud[r2];
			for (auto &x : cur) {
				x = st[x];
			}
			for (auto x : gud[r1]) {
				int s = lower_bound(cur.begin(), cur.end(), st[x]) - cur.begin();
				int e = upper_bound(cur.begin(), cur.end(), en[x]) - cur.begin() - 1;
				if (s <= e) {
					upd(s, 1);
					if (e + 1 < m) {
						upd(e + 1, -1);
					}
				}
			}
			int ans = 0;
			for (int i = 0; i < m; i++) {
				ans += get(i);
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24408 KB Output is correct
2 Correct 5 ms 24408 KB Output is correct
3 Correct 6 ms 24408 KB Output is correct
4 Correct 7 ms 24484 KB Output is correct
5 Correct 8 ms 24408 KB Output is correct
6 Correct 16 ms 24920 KB Output is correct
7 Correct 21 ms 24664 KB Output is correct
8 Correct 28 ms 24920 KB Output is correct
9 Correct 45 ms 25696 KB Output is correct
10 Correct 161 ms 26324 KB Output is correct
11 Correct 179 ms 25732 KB Output is correct
12 Correct 283 ms 27260 KB Output is correct
13 Correct 359 ms 26108 KB Output is correct
14 Correct 304 ms 25840 KB Output is correct
15 Correct 250 ms 28404 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 28280 KB Output is correct
2 Correct 1020 ms 27192 KB Output is correct
3 Correct 1050 ms 30160 KB Output is correct
4 Correct 406 ms 33944 KB Output is correct
5 Correct 326 ms 35292 KB Output is correct
6 Correct 602 ms 34824 KB Output is correct
7 Correct 737 ms 35468 KB Output is correct
8 Correct 687 ms 39948 KB Output is correct
9 Correct 1756 ms 39276 KB Output is correct
10 Correct 2789 ms 44052 KB Output is correct
11 Correct 3084 ms 38128 KB Output is correct
12 Correct 1899 ms 40092 KB Output is correct
13 Correct 1668 ms 40312 KB Output is correct
14 Correct 1921 ms 39844 KB Output is correct
15 Correct 2447 ms 43852 KB Output is correct
16 Correct 2492 ms 49336 KB Output is correct
17 Correct 2109 ms 48380 KB Output is correct