oj.uz

Submission #912804

# Submission time Handle Problem Language Result Execution time Memory
912804 2024-01-19T23:44:09 Z MinaRagy06 Inside information (BOI21_servers) C++17
100 / 100
 2832 ms 440840 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef int64_t ll;
#define SZ(x) (int) x.size()

const int N = 120'005, LOG = 18, B = 550, inf = 1e9;
vector<array<int, 3>> adj[N];
vector<int> dp[N];
int lst;
int solve(int i, int par) {
	if (~dp[i][par]) return dp[i][par];
	int j = (par == SZ(adj[i])? 0 : par + 1);
	dp[i][par] = 1;
	if (j < SZ(adj[i])) {
		if (adj[i][j][1] > lst) return dp[i][par];
		dp[i][par] += solve(adj[i][j][0], adj[i][j][2]) + solve(i, j) - 1;
	}
	return dp[i][par];
}
int st[N], en[N], curt, eulerst[N], euleren[N], eulert;
array<int, 2> par[N];
bool isanc(int u, int v) {
	return st[u] <= st[v] && en[v] <= en[u];
}
struct sparse {
	array<int, 2> a[2 * N][LOG + 1];
	int n;
	int logs[2 * N];
	void build(int _n) {
		n = _n;
		logs[1] = 0;
		for (int j = 2; j <= n; j++) {
			logs[j] = logs[j >> 1] + 1;
		}
		for (int j = 1; j <= LOG; j++) {
			for (int i = 0; i + (1 << (j - 1)) < n; i++) {
				a[i][j] = min(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
			}
		}
	}
	int query(int u, int v) {
		if (st[u] > st[v]) swap(u, v);
		if (isanc(u, v)) {
			return u;
		}
		int l = en[u], r = st[v];
		int lg = logs[r - l + 1];
		array<int, 2> mn = min(a[l][lg], a[r - (1 << lg) + 1][lg]);
		return mn[1];
	}
} lca;
void dfs(int i, int h, int p, int part) {
	lca.a[curt][0] = {h, i};
	st[i] = curt++;
	eulerst[i] = eulert++;
	par[i] = {p, part};
	for (int j = 0; j < SZ(adj[i]); j++) {
		auto [nxt, t, nxtidx] = adj[i][j];
		if (nxt == p) continue;
		dfs(nxt, h + 1, i, t);
		lca.a[curt][0] = {h, i};
		curt++;
	}
	en[i] = curt - 1;
	euleren[i] = eulert - 1;
}
vector<array<int, 2>> ask[N];
int ans[2 * N];
struct sqrt_decomp {
	const int b = 350;
	int a[N], lazy[350];
	int n;
	void init(int _n, int _v) {
		n = _n;
		for (int i = 0; i < n; i++) {
			a[i] = _v;
		}
		for (int i = 0; i <= n / b; i++) {
			lazy[i] = -1;
		}
	}
	void set(int l, int r, int v) {
		int s = l / b, e = r / b;
		if (s == e) {
			for (int i = l; i <= r; i++) {
				a[i] = v;
			}
			return;
		}
		for (int i = s + 1; i <= e - 1; i++) {
			lazy[i] = v;
		}
		int x = s * b, y = (s + 1) * b - 1;
		if (lazy[s] != -1) {
			for (int i = x; i <= y; i++) {
				a[i] = lazy[s];
			}
			lazy[s] = -1;
		}
		for (int i = l; i <= y; i++) {
			a[i] = v;
		}
		x = e * b, y = (e + 1) * b - 1;
		if (lazy[e] != -1) {
			for (int i = x; i <= y; i++) {
				a[i] = lazy[e];
			}
			lazy[e] = -1;
		}
		for (int i = x; i <= r; i++) {
			a[i] = v;
		}
	}
	int get(int i) {
		int x = i / b;
		if (lazy[x] != -1) {
			return lazy[x];
		}
		return a[i];
	}
} Inc, Dec;
set<int> activeinc, activedec;
bool ininc[N], indec[N];
pair<char, vector<int>> v[2 * N];
void process(int i, int p) {
	for (auto [nxt, t, nxtidx] : adj[i]) {
		if (nxt == p) continue;
		process(nxt, i);
	}
	ininc[eulerst[i]] = 1;
	indec[eulerst[i]] = 1;
	for (auto [idx, t] : ask[i]) {
		int a, b;
		if (v[idx].first == 'Q') {
			a = v[idx].second[1], b = v[idx].second[0];
		} else {
			a = v[t].second[0], b = v[t].second[1];
			int x = v[idx].second[0];
			if (isanc(b, x)) {
				a = x;
			} else {
				b = a;
				a = x;
			}
		}
		if (!indec[eulerst[a]] || !ininc[eulerst[b]]) continue;
		int lst1 = Dec.get(eulerst[a]), lst2 = Inc.get(eulerst[b]);
		bool ok = lst1 < lst2;
		int mx;
		if (v[idx].first == 'Q') {
			mx = idx;
		} else {
			mx = t - 1;
		}
		if (b != i) {
			ok &= par[b][1] <= mx;
		} else if (a != i) {
			ok &= lst1 <= mx;
		}
		ans[idx] += ok;
	}
	ask[i].clear();
	if (i == 1) return;
	int part = par[i][1];
	for (auto [nxt, t, nxtidx] : adj[i]) {
		if (nxt == p) continue;
		if (part < t) {
			Inc.set(eulerst[nxt], euleren[nxt], part);
			auto it = activedec.lower_bound(eulerst[nxt]);
			while (it != activedec.end() && *it <= euleren[nxt]) {
				indec[*it] = 0;
				it = activedec.erase(it);
			}
			Dec.set(eulerst[nxt], euleren[nxt], inf);
		} else {
			auto it = activeinc.lower_bound(eulerst[nxt]);
			while (it != activeinc.end() && *it <= euleren[nxt]) {
				ininc[*it] = 0;
				it = activeinc.erase(it);
			}
			Inc.set(eulerst[nxt], euleren[nxt], -inf);
			Dec.set(eulerst[nxt], euleren[nxt], part);
		}
	}
	activeinc.insert(eulerst[i]);
	Inc.set(eulerst[i], eulerst[i], part);
	activedec.insert(eulerst[i]);
	Dec.set(eulerst[i], eulerst[i], part);
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, q;
	cin >> n >> q;
	q += n - 1;
	for (int i = 0; i < q; i++) {
		cin >> v[i].first;
		if (v[i].first == 'S') {
			int a, b;
			cin >> a >> b;
			int x = adj[b].size(), y = adj[a].size();
			adj[a].push_back({b, i, x});
			adj[b].push_back({a, i, y});
			v[i].second = {a, b};
		} else if (v[i].first == 'Q') {
			int a, b;
			cin >> a >> b;
			v[i].second = {a, b};
		} else {
			int a;
			cin >> a;
			v[i].second = {a};
		}
	}
	dfs(1, 0, 1, 0);
	lca.build(curt);
	for (int i = 1; i <= n; i++) {
		dp[i].resize(adj[i].size() + 1);
		for (int j = 0; j <= SZ(adj[i]); j++) {
			dp[i][j] = -1;
		}
	}
	vector<array<int, 3>> upd;
	lst = -1;
	for (int i = 0; i < q; i++) {
		if (upd.size() == B) {
			lst = i - 1;
			upd.clear();
			for (int j = 1; j <= n; j++) {
				for (int k = 0; k <= SZ(adj[j]); k++) {
					dp[j][k] = -1;
				}
			}
		}
		if (v[i].first == 'S') {
			int a = v[i].second[0], b = v[i].second[1];
			if (isanc(b, a)) swap(a, b), swap(v[i].second[0], v[i].second[1]);
			upd.push_back({a, b, i});
		} else if (v[i].first == 'Q') {
			int a = v[i].second[0], b = v[i].second[1];
			int mid = lca.query(a, b);
			ask[mid].push_back({i, -1});
		} else {
			int x = v[i].second[0];
			ans[i] += solve(x, adj[x].size());
			for (auto [a, b, t] : upd) {
				if (isanc(b, x)) {
					ask[b].push_back({i, t});
				} else {
					int mid = lca.query(a, x);
					ask[mid].push_back({i, t});
				}
			}
		}
	}
	Dec.init(eulert, -inf);
	Inc.init(eulert, inf);
	process(1, 1);
	for (int i = 0; i < q; i++) {
		if (v[i].first == 'Q') {
			cout << (ans[i]? "yes\n" : "no\n");
		} else if (v[i].first == 'C') {
			cout << ans[i] << '\n';
		}
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 26508 KB Output is correct
2 Correct 42 ms 28740 KB Output is correct
3 Correct 67 ms 29132 KB Output is correct
4 Correct 49 ms 29180 KB Output is correct
5 Correct 44 ms 29776 KB Output is correct
6 Correct 53 ms 29128 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 26508 KB Output is correct
2 Correct 42 ms 28740 KB Output is correct
3 Correct 67 ms 29132 KB Output is correct
4 Correct 49 ms 29180 KB Output is correct
5 Correct 44 ms 29776 KB Output is correct
6 Correct 53 ms 29128 KB Output is correct
7 Correct 35 ms 29240 KB Output is correct
8 Correct 527 ms 218528 KB Output is correct
9 Correct 500 ms 186080 KB Output is correct
10 Correct 515 ms 174412 KB Output is correct
11 Correct 257 ms 118688 KB Output is correct
12 Correct 232 ms 159124 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 26148 KB Output is correct
2 Correct 414 ms 87320 KB Output is correct
3 Correct 344 ms 87556 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 26148 KB Output is correct
2 Correct 414 ms 87320 KB Output is correct
3 Correct 344 ms 87556 KB Output is correct
4 Correct 40 ms 29384 KB Output is correct
5 Correct 1355 ms 146116 KB Output is correct
6 Correct 2107 ms 350272 KB Output is correct
7 Correct 1939 ms 348036 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26456 KB Output is correct
2 Correct 464 ms 90624 KB Output is correct
3 Correct 385 ms 90760 KB Output is correct
4 Correct 312 ms 95872 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26456 KB Output is correct
2 Correct 464 ms 90624 KB Output is correct
3 Correct 385 ms 90760 KB Output is correct
4 Correct 312 ms 95872 KB Output is correct
5 Correct 37 ms 29100 KB Output is correct
6 Correct 1215 ms 275520 KB Output is correct
7 Correct 1172 ms 281392 KB Output is correct
8 Correct 1881 ms 440360 KB Output is correct
9 Correct 1855 ms 439852 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 26188 KB Output is correct
2 Correct 302 ms 82368 KB Output is correct
3 Correct 375 ms 77312 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 26188 KB Output is correct
2 Correct 302 ms 82368 KB Output is correct
3 Correct 375 ms 77312 KB Output is correct
4 Correct 37 ms 28876 KB Output is correct
5 Correct 800 ms 190764 KB Output is correct
6 Correct 1131 ms 237756 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26460 KB Output is correct
2 Correct 393 ms 90708 KB Output is correct
3 Correct 372 ms 90688 KB Output is correct
4 Correct 320 ms 96080 KB Output is correct
5 Correct 28 ms 26200 KB Output is correct
6 Correct 314 ms 82440 KB Output is correct
7 Correct 347 ms 77228 KB Output is correct
8 Correct 362 ms 77192 KB Output is correct
9 Correct 398 ms 77648 KB Output is correct
10 Correct 535 ms 88884 KB Output is correct
11 Correct 511 ms 87588 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26460 KB Output is correct
2 Correct 393 ms 90708 KB Output is correct
3 Correct 372 ms 90688 KB Output is correct
4 Correct 320 ms 96080 KB Output is correct
5 Correct 28 ms 26200 KB Output is correct
6 Correct 314 ms 82440 KB Output is correct
7 Correct 347 ms 77228 KB Output is correct
8 Correct 362 ms 77192 KB Output is correct
9 Correct 398 ms 77648 KB Output is correct
10 Correct 535 ms 88884 KB Output is correct
11 Correct 511 ms 87588 KB Output is correct
12 Correct 34 ms 29132 KB Output is correct
13 Correct 1263 ms 275632 KB Output is correct
14 Correct 1180 ms 281576 KB Output is correct
15 Correct 1736 ms 440840 KB Output is correct
16 Correct 1750 ms 440212 KB Output is correct
17 Correct 36 ms 28868 KB Output is correct
18 Correct 743 ms 190756 KB Output is correct
19 Correct 1123 ms 237300 KB Output is correct
20 Correct 818 ms 147984 KB Output is correct
21 Correct 1249 ms 238480 KB Output is correct
22 Correct 1824 ms 374004 KB Output is correct
23 Correct 2803 ms 267616 KB Output is correct
24 Correct 1369 ms 122556 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 26448 KB Output is correct
2 Correct 39 ms 28908 KB Output is correct
3 Correct 39 ms 29132 KB Output is correct
4 Correct 42 ms 29132 KB Output is correct
5 Correct 57 ms 29776 KB Output is correct
6 Correct 37 ms 29124 KB Output is correct
7 Correct 28 ms 26064 KB Output is correct
8 Correct 306 ms 87428 KB Output is correct
9 Correct 298 ms 87556 KB Output is correct
10 Correct 30 ms 26460 KB Output is correct
11 Correct 408 ms 90836 KB Output is correct
12 Correct 399 ms 90752 KB Output is correct
13 Correct 325 ms 96036 KB Output is correct
14 Correct 29 ms 26200 KB Output is correct
15 Correct 298 ms 82464 KB Output is correct
16 Correct 367 ms 77468 KB Output is correct
17 Correct 365 ms 77588 KB Output is correct
18 Correct 385 ms 77596 KB Output is correct
19 Correct 557 ms 88668 KB Output is correct
20 Correct 507 ms 87240 KB Output is correct
21 Correct 318 ms 84708 KB Output is correct
22 Correct 360 ms 84604 KB Output is correct
23 Correct 329 ms 78436 KB Output is correct
24 Correct 371 ms 78780 KB Output is correct
25 Correct 387 ms 85776 KB Output is correct
26 Correct 426 ms 81496 KB Output is correct
27 Correct 382 ms 81868 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 26448 KB Output is correct
2 Correct 39 ms 28908 KB Output is correct
3 Correct 39 ms 29132 KB Output is correct
4 Correct 42 ms 29132 KB Output is correct
5 Correct 57 ms 29776 KB Output is correct
6 Correct 37 ms 29124 KB Output is correct
7 Correct 28 ms 26064 KB Output is correct
8 Correct 306 ms 87428 KB Output is correct
9 Correct 298 ms 87556 KB Output is correct
10 Correct 30 ms 26460 KB Output is correct
11 Correct 408 ms 90836 KB Output is correct
12 Correct 399 ms 90752 KB Output is correct
13 Correct 325 ms 96036 KB Output is correct
14 Correct 29 ms 26200 KB Output is correct
15 Correct 298 ms 82464 KB Output is correct
16 Correct 367 ms 77468 KB Output is correct
17 Correct 365 ms 77588 KB Output is correct
18 Correct 385 ms 77596 KB Output is correct
19 Correct 557 ms 88668 KB Output is correct
20 Correct 507 ms 87240 KB Output is correct
21 Correct 318 ms 84708 KB Output is correct
22 Correct 360 ms 84604 KB Output is correct
23 Correct 329 ms 78436 KB Output is correct
24 Correct 371 ms 78780 KB Output is correct
25 Correct 387 ms 85776 KB Output is correct
26 Correct 426 ms 81496 KB Output is correct
27 Correct 382 ms 81868 KB Output is correct
28 Correct 37 ms 29244 KB Output is correct
29 Correct 505 ms 216752 KB Output is correct
30 Correct 369 ms 189016 KB Output is correct
31 Correct 480 ms 175612 KB Output is correct
32 Correct 226 ms 118840 KB Output is correct
33 Correct 221 ms 159892 KB Output is correct
34 Correct 38 ms 29632 KB Output is correct
35 Correct 1045 ms 146300 KB Output is correct
36 Correct 1598 ms 351332 KB Output is correct
37 Correct 1536 ms 347520 KB Output is correct
38 Correct 35 ms 29132 KB Output is correct
39 Correct 1206 ms 275704 KB Output is correct
40 Correct 1084 ms 281420 KB Output is correct
41 Correct 1798 ms 440424 KB Output is correct
42 Correct 1806 ms 439852 KB Output is correct
43 Correct 35 ms 28800 KB Output is correct
44 Correct 730 ms 185796 KB Output is correct
45 Correct 1076 ms 238360 KB Output is correct
46 Correct 829 ms 147120 KB Output is correct
47 Correct 1334 ms 240644 KB Output is correct
48 Correct 1758 ms 373784 KB Output is correct
49 Correct 2832 ms 267116 KB Output is correct
50 Correct 1370 ms 121896 KB Output is correct
51 Correct 1243 ms 385388 KB Output is correct
52 Correct 1527 ms 349292 KB Output is correct
53 Correct 1553 ms 350512 KB Output is correct
54 Correct 1519 ms 351884 KB Output is correct
55 Correct 1152 ms 350784 KB Output is correct
56 Correct 727 ms 279388 KB Output is correct
57 Correct 1238 ms 358328 KB Output is correct
58 Correct 1454 ms 329308 KB Output is correct
59 Correct 527 ms 110212 KB Output is correct