oj.uz

Submission #895436

# Submission time Handle Problem Language Result Execution time Memory
895436 2023-12-30T00:11:36 Z MinaRagy06 Regions (IOI09_regions) C++17
100 / 100
 4443 ms 74000 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 << 22) && 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 4 ms 24408 KB Output is correct
3 Correct 7 ms 24408 KB Output is correct
4 Correct 7 ms 24408 KB Output is correct
5 Correct 10 ms 24408 KB Output is correct
6 Correct 14 ms 24920 KB Output is correct
7 Correct 22 ms 24736 KB Output is correct
8 Correct 30 ms 24920 KB Output is correct
9 Correct 57 ms 25696 KB Output is correct
10 Correct 167 ms 26316 KB Output is correct
11 Correct 190 ms 25740 KB Output is correct
12 Correct 317 ms 27160 KB Output is correct
13 Correct 391 ms 26112 KB Output is correct
14 Correct 323 ms 25872 KB Output is correct
15 Correct 293 ms 28496 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 28244 KB Output is correct
2 Correct 1614 ms 27196 KB Output is correct
3 Correct 1306 ms 30240 KB Output is correct
4 Correct 1349 ms 58576 KB Output is correct
5 Correct 650 ms 60092 KB Output is correct
6 Correct 1517 ms 59492 KB Output is correct
7 Correct 1594 ms 60336 KB Output is correct
8 Correct 1192 ms 64572 KB Output is correct
9 Correct 2598 ms 63944 KB Output is correct
10 Correct 1849 ms 68320 KB Output is correct
11 Correct 4148 ms 62792 KB Output is correct
12 Correct 4443 ms 64776 KB Output is correct
13 Correct 2827 ms 65132 KB Output is correct
14 Correct 3449 ms 64428 KB Output is correct
15 Correct 2372 ms 68504 KB Output is correct
16 Correct 2261 ms 74000 KB Output is correct
17 Correct 2408 ms 72860 KB Output is correct