oj.uz

Submission #895426

# Submission time Handle Problem Language Result Execution time Memory
895426 2023-12-29T23:52:41 Z MinaRagy06 Regions (IOI09_regions) C++17
30 / 100
 8000 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 cnt = (1 << 24) / 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 5 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 15 ms 24920 KB Output is correct
7 Correct 21 ms 24664 KB Output is correct
8 Correct 28 ms 24920 KB Output is correct
9 Correct 49 ms 25704 KB Output is correct
10 Correct 159 ms 26324 KB Output is correct
11 Correct 176 ms 25728 KB Output is correct
12 Correct 284 ms 27160 KB Output is correct
13 Correct 390 ms 26112 KB Output is correct
14 Correct 321 ms 25856 KB Output is correct
15 Correct 235 ms 28532 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 28184 KB Output is correct
2 Correct 1122 ms 27032 KB Output is correct
3 Correct 1081 ms 30164 KB Output is correct
4 Runtime error 3559 ms 131072 KB Execution killed with signal 9
5 Runtime error 1604 ms 131072 KB Execution killed with signal 9
6 Runtime error 3685 ms 131072 KB Execution killed with signal 9
7 Runtime error 3457 ms 131072 KB Execution killed with signal 9
8 Runtime error 2357 ms 131072 KB Execution killed with signal 9
9 Runtime error 5296 ms 131072 KB Execution killed with signal 9
10 Runtime error 1869 ms 131072 KB Execution killed with signal 9
11 Runtime error 4051 ms 131072 KB Execution killed with signal 9
12 Execution timed out 8022 ms 103680 KB Time limit exceeded
13 Runtime error 6185 ms 131072 KB Execution killed with signal 9
14 Execution timed out 8013 ms 120648 KB Time limit exceeded
15 Runtime error 2748 ms 131072 KB Execution killed with signal 9
16 Runtime error 2497 ms 131072 KB Execution killed with signal 9
17 Runtime error 2732 ms 131072 KB Execution killed with signal 9