oj.uz

Submission #895438

# Submission time Handle Problem Language Result Execution time Memory
895438 2023-12-30T00:14:23 Z MinaRagy06 Regions (IOI09_regions) C++17
100 / 100
 2994 ms 49344 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 ttl = 0, ttl2 = 0;
	for (int i = 0; i < r; i++) {
		if (!(ttl + r < (1 << 20) && ttl2 + n + r < int(1e8))) {
			break;
		}
		idx[order[i]] = i;
		above[i].resize(r);
		below[i].resize(r);
		ttl += r;
		ttl2 += n + 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 6 ms 24408 KB Output is correct
5 Correct 9 ms 24408 KB Output is correct
6 Correct 14 ms 24920 KB Output is correct
7 Correct 24 ms 24664 KB Output is correct
8 Correct 27 ms 24920 KB Output is correct
9 Correct 53 ms 25700 KB Output is correct
10 Correct 156 ms 26316 KB Output is correct
11 Correct 191 ms 25736 KB Output is correct
12 Correct 301 ms 27160 KB Output is correct
13 Correct 405 ms 26192 KB Output is correct
14 Correct 314 ms 25936 KB Output is correct
15 Correct 241 ms 28632 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 28164 KB Output is correct
2 Correct 1087 ms 27032 KB Output is correct
3 Correct 1104 ms 30164 KB Output is correct
4 Correct 417 ms 33944 KB Output is correct
5 Correct 348 ms 35344 KB Output is correct
6 Correct 601 ms 34820 KB Output is correct
7 Correct 758 ms 35636 KB Output is correct
8 Correct 714 ms 39676 KB Output is correct
9 Correct 1686 ms 39412 KB Output is correct
10 Correct 2936 ms 43900 KB Output is correct
11 Correct 2994 ms 38244 KB Output is correct
12 Correct 1652 ms 40484 KB Output is correct
13 Correct 1662 ms 40496 KB Output is correct
14 Correct 1830 ms 39916 KB Output is correct
15 Correct 2366 ms 43844 KB Output is correct
16 Correct 2562 ms 49344 KB Output is correct
17 Correct 2063 ms 48272 KB Output is correct