oj.uz

Submission #895442

# Submission time Handle Problem Language Result Execution time Memory
895442 2023-12-30T00:17:46 Z MinaRagy06 Regions (IOI09_regions) C++17
100 / 100
 3326 ms 53104 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 < int(1.5e6) && 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 24404 KB Output is correct
3 Correct 6 ms 24408 KB Output is correct
4 Correct 6 ms 24408 KB Output is correct
5 Correct 10 ms 24408 KB Output is correct
6 Correct 16 ms 24920 KB Output is correct
7 Correct 26 ms 24664 KB Output is correct
8 Correct 27 ms 24920 KB Output is correct
9 Correct 55 ms 25696 KB Output is correct
10 Correct 165 ms 26320 KB Output is correct
11 Correct 184 ms 25736 KB Output is correct
12 Correct 300 ms 27160 KB Output is correct
13 Correct 376 ms 26120 KB Output is correct
14 Correct 312 ms 25908 KB Output is correct
15 Correct 266 ms 28488 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 789 ms 28208 KB Output is correct
2 Correct 1095 ms 27160 KB Output is correct
3 Correct 1110 ms 30156 KB Output is correct
4 Correct 534 ms 37456 KB Output is correct
5 Correct 378 ms 39156 KB Output is correct
6 Correct 772 ms 38388 KB Output is correct
7 Correct 873 ms 38988 KB Output is correct
8 Correct 825 ms 43556 KB Output is correct
9 Correct 1744 ms 42800 KB Output is correct
10 Correct 2535 ms 47188 KB Output is correct
11 Correct 3326 ms 41648 KB Output is correct
12 Correct 2137 ms 43612 KB Output is correct
13 Correct 1769 ms 43800 KB Output is correct
14 Correct 2029 ms 43300 KB Output is correct
15 Correct 2320 ms 47368 KB Output is correct
16 Correct 2451 ms 53104 KB Output is correct
17 Correct 2214 ms 51936 KB Output is correct