oj.uz

Submission #895437

# Submission time Handle Problem Language Result Execution time Memory
895437 2023-12-30T00:12:35 Z MinaRagy06 Regions (IOI09_regions) C++17
95 / 100
 6708 ms 131072 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 << 24) && 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 8 ms 24408 KB Output is correct
5 Correct 8 ms 24408 KB Output is correct
6 Correct 16 ms 24920 KB Output is correct
7 Correct 22 ms 24664 KB Output is correct
8 Correct 28 ms 24920 KB Output is correct
9 Correct 45 ms 25704 KB Output is correct
10 Correct 162 ms 26316 KB Output is correct
11 Correct 180 ms 25736 KB Output is correct
12 Correct 295 ms 27156 KB Output is correct
13 Correct 391 ms 26108 KB Output is correct
14 Correct 307 ms 25916 KB Output is correct
15 Correct 277 ms 28500 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 871 ms 28812 KB Output is correct
2 Correct 1062 ms 27192 KB Output is correct
3 Correct 1114 ms 30656 KB Output is correct
4 Correct 3391 ms 118008 KB Output is correct
5 Correct 1679 ms 120532 KB Output is correct
6 Correct 3609 ms 119524 KB Output is correct
7 Correct 3891 ms 125500 KB Output is correct
8 Correct 2013 ms 102992 KB Output is correct
9 Correct 4360 ms 102356 KB Output is correct
10 Runtime error 1776 ms 131072 KB Execution killed with signal 9
11 Correct 5031 ms 117044 KB Output is correct
12 Correct 6708 ms 92540 KB Output is correct
13 Correct 4131 ms 92724 KB Output is correct
14 Correct 6097 ms 102796 KB Output is correct
15 Correct 3079 ms 122720 KB Output is correct
16 Correct 3269 ms 128140 KB Output is correct
17 Correct 3076 ms 111224 KB Output is correct