oj.uz

Submission #895435

# Submission time Handle Problem Language Result Execution time Memory
895435 2023-12-30T00:10:25 Z MinaRagy06 Regions (IOI09_regions) C++17
70 / 100
 8000 ms 74088 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 << 22) && ttl2 + n + r < int(1e8) && 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;
		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 24492 KB Output is correct
3 Correct 6 ms 24512 KB Output is correct
4 Correct 8 ms 24408 KB Output is correct
5 Correct 9 ms 24408 KB Output is correct
6 Correct 18 ms 24920 KB Output is correct
7 Correct 25 ms 24664 KB Output is correct
8 Correct 27 ms 24920 KB Output is correct
9 Correct 48 ms 25688 KB Output is correct
10 Correct 192 ms 26320 KB Output is correct
11 Correct 194 ms 25736 KB Output is correct
12 Correct 295 ms 27156 KB Output is correct
13 Correct 387 ms 26112 KB Output is correct
14 Correct 321 ms 25796 KB Output is correct
15 Correct 251 ms 28352 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8036 ms 28024 KB Time limit exceeded
2 Execution timed out 8016 ms 27096 KB Time limit exceeded
3 Correct 1914 ms 29696 KB Output is correct
4 Correct 1270 ms 58576 KB Output is correct
5 Correct 771 ms 60100 KB Output is correct
6 Correct 1499 ms 59492 KB Output is correct
7 Correct 1658 ms 60328 KB Output is correct
8 Correct 1239 ms 64576 KB Output is correct
9 Correct 2884 ms 64052 KB Output is correct
10 Correct 1658 ms 68328 KB Output is correct
11 Correct 4292 ms 62792 KB Output is correct
12 Correct 4270 ms 64776 KB Output is correct
13 Execution timed out 8080 ms 32288 KB Time limit exceeded
14 Execution timed out 8063 ms 31880 KB Time limit exceeded
15 Execution timed out 8067 ms 34784 KB Time limit exceeded
16 Correct 3016 ms 74088 KB Output is correct
17 Execution timed out 8047 ms 40288 KB Time limit exceeded