oj.uz

Submission #895440

# Submission time Handle Problem Language Result Execution time Memory
895440 2023-12-30T00:16:24 Z MinaRagy06 Regions (IOI09_regions) C++17
100 / 100
 3409 ms 46600 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(7e5) && 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 7 ms 24408 KB Output is correct
5 Correct 8 ms 24408 KB Output is correct
6 Correct 17 ms 24920 KB Output is correct
7 Correct 19 ms 24664 KB Output is correct
8 Correct 28 ms 24920 KB Output is correct
9 Correct 50 ms 25700 KB Output is correct
10 Correct 162 ms 26320 KB Output is correct
11 Correct 191 ms 25740 KB Output is correct
12 Correct 296 ms 27296 KB Output is correct
13 Correct 389 ms 26112 KB Output is correct
14 Correct 313 ms 25988 KB Output is correct
15 Correct 303 ms 28536 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 831 ms 28176 KB Output is correct
2 Correct 1067 ms 27120 KB Output is correct
3 Correct 1134 ms 30164 KB Output is correct
4 Correct 318 ms 31188 KB Output is correct
5 Correct 285 ms 32560 KB Output is correct
6 Correct 575 ms 32080 KB Output is correct
7 Correct 660 ms 32732 KB Output is correct
8 Correct 829 ms 37168 KB Output is correct
9 Correct 1887 ms 36576 KB Output is correct
10 Correct 3409 ms 40924 KB Output is correct
11 Correct 3343 ms 35392 KB Output is correct
12 Correct 1660 ms 37784 KB Output is correct
13 Correct 1898 ms 37540 KB Output is correct
14 Correct 2015 ms 37028 KB Output is correct
15 Correct 3011 ms 41104 KB Output is correct
16 Correct 2711 ms 46600 KB Output is correct
17 Correct 2475 ms 45456 KB Output is correct