oj.uz

Submission #895434

# Submission time Handle Problem Language Result Execution time Memory
895434 2023-12-30T00:08:33 Z MinaRagy06 Regions (IOI09_regions) C++17
75 / 100
 8000 ms 74244 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;
	for (int i = 0; i < r; i++) {
		if (!(ttl + r < (1 << 22) && n + r < q * sz[order[i]] * __lg(sz[order[i]]))) {
			break;
		}
		idx[order[i]] = i;
		above[i].resize(r);
		below[i].resize(r);
		ttl += 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 7 ms 24408 KB Output is correct
5 Correct 11 ms 24408 KB Output is correct
6 Correct 15 ms 24920 KB Output is correct
7 Correct 27 ms 24664 KB Output is correct
8 Correct 28 ms 24920 KB Output is correct
9 Correct 50 ms 25696 KB Output is correct
10 Correct 178 ms 26324 KB Output is correct
11 Correct 197 ms 25740 KB Output is correct
12 Correct 343 ms 27160 KB Output is correct
13 Correct 386 ms 26112 KB Output is correct
14 Correct 329 ms 25936 KB Output is correct
15 Correct 256 ms 28376 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8079 ms 27876 KB Time limit exceeded
2 Execution timed out 8010 ms 26832 KB Time limit exceeded
3 Correct 1978 ms 29664 KB Output is correct
4 Correct 1280 ms 58580 KB Output is correct
5 Correct 669 ms 60100 KB Output is correct
6 Correct 1563 ms 59492 KB Output is correct
7 Correct 1597 ms 60132 KB Output is correct
8 Correct 1174 ms 64576 KB Output is correct
9 Correct 2760 ms 64212 KB Output is correct
10 Correct 1803 ms 68324 KB Output is correct
11 Correct 3873 ms 62988 KB Output is correct
12 Correct 3953 ms 64880 KB Output is correct
13 Correct 6995 ms 32164 KB Output is correct
14 Execution timed out 8048 ms 31660 KB Time limit exceeded
15 Execution timed out 8077 ms 34864 KB Time limit exceeded
16 Correct 2488 ms 74244 KB Output is correct
17 Execution timed out 8048 ms 40364 KB Time limit exceeded