oj.uz

Submission #895441

# Submission time Handle Problem Language Result Execution time Memory
895441 2023-12-30T00:16:37 Z MinaRagy06 Regions (IOI09_regions) C++17
100 / 100
 3688 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 6 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 10 ms 24408 KB Output is correct
6 Correct 15 ms 24920 KB Output is correct
7 Correct 24 ms 24676 KB Output is correct
8 Correct 31 ms 24920 KB Output is correct
9 Correct 55 ms 25700 KB Output is correct
10 Correct 188 ms 26328 KB Output is correct
11 Correct 190 ms 25732 KB Output is correct
12 Correct 286 ms 27156 KB Output is correct
13 Correct 408 ms 26108 KB Output is correct
14 Correct 372 ms 25916 KB Output is correct
15 Correct 261 ms 28620 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 877 ms 28284 KB Output is correct
2 Correct 1154 ms 26988 KB Output is correct
3 Correct 1188 ms 30160 KB Output is correct
4 Correct 353 ms 31184 KB Output is correct
5 Correct 330 ms 32568 KB Output is correct
6 Correct 553 ms 32080 KB Output is correct
7 Correct 738 ms 32976 KB Output is correct
8 Correct 870 ms 37168 KB Output is correct
9 Correct 2077 ms 36788 KB Output is correct
10 Correct 3502 ms 40924 KB Output is correct
11 Correct 3688 ms 35420 KB Output is correct
12 Correct 1636 ms 37336 KB Output is correct
13 Correct 1795 ms 37540 KB Output is correct
14 Correct 1649 ms 37028 KB Output is correct
15 Correct 2506 ms 41316 KB Output is correct
16 Correct 2544 ms 46600 KB Output is correct
17 Correct 2418 ms 45460 KB Output is correct