oj.uz

Submission #895439

# Submission time Handle Problem Language Result Execution time Memory
895439 2023-12-30T00:15:27 Z MinaRagy06 Regions (IOI09_regions) C++17
100 / 100
 3557 ms 45268 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 << 19) && 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 7 ms 24408 KB Output is correct
3 Correct 6 ms 24408 KB Output is correct
4 Correct 7 ms 24496 KB Output is correct
5 Correct 10 ms 24408 KB Output is correct
6 Correct 15 ms 24920 KB Output is correct
7 Correct 21 ms 24664 KB Output is correct
8 Correct 26 ms 24920 KB Output is correct
9 Correct 48 ms 25708 KB Output is correct
10 Correct 176 ms 26424 KB Output is correct
11 Correct 177 ms 25744 KB Output is correct
12 Correct 281 ms 27160 KB Output is correct
13 Correct 383 ms 26120 KB Output is correct
14 Correct 337 ms 26180 KB Output is correct
15 Correct 232 ms 28500 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 28168 KB Output is correct
2 Correct 1084 ms 27444 KB Output is correct
3 Correct 1048 ms 30160 KB Output is correct
4 Correct 270 ms 29836 KB Output is correct
5 Correct 294 ms 31152 KB Output is correct
6 Correct 443 ms 30708 KB Output is correct
7 Correct 619 ms 31912 KB Output is correct
8 Correct 763 ms 35844 KB Output is correct
9 Correct 1733 ms 35172 KB Output is correct
10 Correct 3557 ms 39556 KB Output is correct
11 Correct 3156 ms 34020 KB Output is correct
12 Correct 1496 ms 35964 KB Output is correct
13 Correct 1480 ms 36416 KB Output is correct
14 Correct 1622 ms 35772 KB Output is correct
15 Correct 2569 ms 39732 KB Output is correct
16 Correct 2494 ms 45268 KB Output is correct
17 Correct 2176 ms 44168 KB Output is correct