oj.uz

Submission #895429

# Submission time Handle Problem Language Result Execution time Memory
895429 2023-12-29T23:57:05 Z MinaRagy06 Regions (IOI09_regions) C++17
100 / 100
 4601 ms 74100 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 << 22) / 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 6 ms 24404 KB Output is correct
5 Correct 8 ms 24408 KB Output is correct
6 Correct 17 ms 24920 KB Output is correct
7 Correct 23 ms 24664 KB Output is correct
8 Correct 25 ms 24920 KB Output is correct
9 Correct 48 ms 25696 KB Output is correct
10 Correct 157 ms 26320 KB Output is correct
11 Correct 180 ms 25728 KB Output is correct
12 Correct 288 ms 27308 KB Output is correct
13 Correct 385 ms 26116 KB Output is correct
14 Correct 311 ms 26008 KB Output is correct
15 Correct 232 ms 28496 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 28240 KB Output is correct
2 Correct 1123 ms 27112 KB Output is correct
3 Correct 1118 ms 30304 KB Output is correct
4 Correct 1272 ms 58580 KB Output is correct
5 Correct 717 ms 60092 KB Output is correct
6 Correct 1422 ms 59496 KB Output is correct
7 Correct 1505 ms 60132 KB Output is correct
8 Correct 1189 ms 64580 KB Output is correct
9 Correct 2537 ms 64044 KB Output is correct
10 Correct 1748 ms 68516 KB Output is correct
11 Correct 4050 ms 62956 KB Output is correct
12 Correct 4601 ms 64776 KB Output is correct
13 Correct 2730 ms 64976 KB Output is correct
14 Correct 3698 ms 64432 KB Output is correct
15 Correct 2583 ms 68500 KB Output is correct
16 Correct 2416 ms 74100 KB Output is correct
17 Correct 2484 ms 72860 KB Output is correct