oj.uz

Submission #895433

# Submission time Handle Problem Language Result Execution time Memory
895433 2023-12-30T00:07:44 Z MinaRagy06 Regions (IOI09_regions) C++17
75 / 100
 8000 ms 43760 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[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 5 ms 24408 KB Output is correct
3 Correct 6 ms 24408 KB Output is correct
4 Correct 7 ms 24492 KB Output is correct
5 Correct 8 ms 24496 KB Output is correct
6 Correct 12 ms 24408 KB Output is correct
7 Correct 21 ms 24664 KB Output is correct
8 Correct 30 ms 25172 KB Output is correct
9 Correct 45 ms 25700 KB Output is correct
10 Correct 158 ms 26316 KB Output is correct
11 Correct 174 ms 25728 KB Output is correct
12 Correct 275 ms 27156 KB Output is correct
13 Correct 389 ms 26116 KB Output is correct
14 Correct 310 ms 25872 KB Output is correct
15 Correct 276 ms 28380 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8045 ms 27848 KB Time limit exceeded
2 Execution timed out 8053 ms 27084 KB Time limit exceeded
3 Correct 1168 ms 30288 KB Output is correct
4 Correct 172 ms 25968 KB Output is correct
5 Correct 230 ms 27088 KB Output is correct
6 Correct 1085 ms 26416 KB Output is correct
7 Correct 1045 ms 43760 KB Output is correct
8 Correct 1067 ms 30952 KB Output is correct
9 Correct 1637 ms 30644 KB Output is correct
10 Correct 3816 ms 36012 KB Output is correct
11 Correct 2666 ms 30064 KB Output is correct
12 Correct 3126 ms 32296 KB Output is correct
13 Correct 3979 ms 32336 KB Output is correct
14 Correct 5154 ms 31944 KB Output is correct
15 Execution timed out 8064 ms 35068 KB Time limit exceeded
16 Execution timed out 8071 ms 38456 KB Time limit exceeded
17 Execution timed out 8087 ms 40292 KB Time limit exceeded