oj.uz

Submission #912800

# Submission time Handle Problem Language Result Execution time Memory
912800 2024-01-19T23:39:24 Z MinaRagy06 Inside information (BOI21_servers) C++17
100 / 100
 2938 ms 411084 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 = 500, 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;
	}
// 	for (auto [a, b, t, idx] : ask[i]) {
// 		if (!indec[eulerst[a]] || !ininc[eulerst[b]]) continue;
// 		int lst1 = Dec.get(eulerst[a]), lst2 = Inc.get(eulerst[b]);
// 		bool ok = lst1 < lst2;
// 		if (b != i) {
// 			ok &= par[b][1] <= t;
// 		} else if (a != i) {
// 			ok &= lst1 <= t;
// 		}
// 		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({b, a, i, i});
			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({x, b, t - 1, i});
// 				} else {
// 					int mid = lca.query(a, x);
// 					ask[mid].push_back({x, a, t - 1, i});
// 				}
// 			}

			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});
				}
			}

// 			for (auto [a, b, t, idx] : ask[i]) {
// 				if (!indec[eulerst[a]] || !ininc[eulerst[b]]) continue;
// 				int lst1 = Dec.get(eulerst[a]), lst2 = Inc.get(eulerst[b]);
// 				bool ok = lst1 < lst2;
// 				if (b != i) {
// 					ok &= par[b][1] <= t;
// 				} else if (a != i) {
// 					ok &= lst1 <= t;
// 				}
// 				ans[idx] += ok;
// 			}
		}
	}
	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 28 ms 26448 KB Output is correct
2 Correct 40 ms 28880 KB Output is correct
3 Correct 39 ms 29132 KB Output is correct
4 Correct 49 ms 29132 KB Output is correct
5 Correct 41 ms 29780 KB Output is correct
6 Correct 35 ms 29128 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26448 KB Output is correct
2 Correct 40 ms 28880 KB Output is correct
3 Correct 39 ms 29132 KB Output is correct
4 Correct 49 ms 29132 KB Output is correct
5 Correct 41 ms 29780 KB Output is correct
6 Correct 35 ms 29128 KB Output is correct
7 Correct 35 ms 29244 KB Output is correct
8 Correct 481 ms 201504 KB Output is correct
9 Correct 341 ms 178100 KB Output is correct
10 Correct 475 ms 167308 KB Output is correct
11 Correct 588 ms 309416 KB Output is correct
12 Correct 453 ms 290724 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26064 KB Output is correct
2 Correct 354 ms 87324 KB Output is correct
3 Correct 402 ms 87612 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26064 KB Output is correct
2 Correct 354 ms 87324 KB Output is correct
3 Correct 402 ms 87612 KB Output is correct
4 Correct 34 ms 29776 KB Output is correct
5 Correct 995 ms 146332 KB Output is correct
6 Correct 1897 ms 343492 KB Output is correct
7 Correct 1285 ms 343752 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 26472 KB Output is correct
2 Correct 479 ms 90812 KB Output is correct
3 Correct 435 ms 90724 KB Output is correct
4 Correct 341 ms 96104 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 26472 KB Output is correct
2 Correct 479 ms 90812 KB Output is correct
3 Correct 435 ms 90724 KB Output is correct
4 Correct 341 ms 96104 KB Output is correct
5 Correct 33 ms 29064 KB Output is correct
6 Correct 1257 ms 257952 KB Output is correct
7 Correct 1188 ms 263928 KB Output is correct
8 Correct 1866 ms 410832 KB Output is correct
9 Correct 1697 ms 410696 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26188 KB Output is correct
2 Correct 306 ms 82248 KB Output is correct
3 Correct 369 ms 77468 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26188 KB Output is correct
2 Correct 306 ms 82248 KB Output is correct
3 Correct 369 ms 77468 KB Output is correct
4 Correct 35 ms 28868 KB Output is correct
5 Correct 953 ms 301496 KB Output is correct
6 Correct 1051 ms 233312 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 26448 KB Output is correct
2 Correct 394 ms 90704 KB Output is correct
3 Correct 388 ms 90708 KB Output is correct
4 Correct 326 ms 95828 KB Output is correct
5 Correct 29 ms 26292 KB Output is correct
6 Correct 313 ms 82324 KB Output is correct
7 Correct 358 ms 77388 KB Output is correct
8 Correct 368 ms 77228 KB Output is correct
9 Correct 398 ms 77616 KB Output is correct
10 Correct 545 ms 88656 KB Output is correct
11 Correct 500 ms 87220 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 26448 KB Output is correct
2 Correct 394 ms 90704 KB Output is correct
3 Correct 388 ms 90708 KB Output is correct
4 Correct 326 ms 95828 KB Output is correct
5 Correct 29 ms 26292 KB Output is correct
6 Correct 313 ms 82324 KB Output is correct
7 Correct 358 ms 77388 KB Output is correct
8 Correct 368 ms 77228 KB Output is correct
9 Correct 398 ms 77616 KB Output is correct
10 Correct 545 ms 88656 KB Output is correct
11 Correct 500 ms 87220 KB Output is correct
12 Correct 35 ms 29140 KB Output is correct
13 Correct 1167 ms 258040 KB Output is correct
14 Correct 1107 ms 263720 KB Output is correct
15 Correct 1603 ms 411084 KB Output is correct
16 Correct 1664 ms 410688 KB Output is correct
17 Correct 35 ms 28872 KB Output is correct
18 Correct 963 ms 300936 KB Output is correct
19 Correct 1070 ms 235524 KB Output is correct
20 Correct 1578 ms 373912 KB Output is correct
21 Correct 1244 ms 232952 KB Output is correct
22 Correct 1759 ms 348428 KB Output is correct
23 Correct 2938 ms 267052 KB Output is correct
24 Correct 1395 ms 120980 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26440 KB Output is correct
2 Correct 37 ms 28872 KB Output is correct
3 Correct 39 ms 29140 KB Output is correct
4 Correct 39 ms 29124 KB Output is correct
5 Correct 47 ms 29780 KB Output is correct
6 Correct 36 ms 29128 KB Output is correct
7 Correct 28 ms 26060 KB Output is correct
8 Correct 348 ms 87404 KB Output is correct
9 Correct 321 ms 87300 KB Output is correct
10 Correct 27 ms 26544 KB Output is correct
11 Correct 396 ms 90580 KB Output is correct
12 Correct 389 ms 90632 KB Output is correct
13 Correct 323 ms 95824 KB Output is correct
14 Correct 29 ms 26196 KB Output is correct
15 Correct 317 ms 82380 KB Output is correct
16 Correct 347 ms 77396 KB Output is correct
17 Correct 368 ms 77232 KB Output is correct
18 Correct 392 ms 77652 KB Output is correct
19 Correct 538 ms 88568 KB Output is correct
20 Correct 541 ms 87256 KB Output is correct
21 Correct 336 ms 84596 KB Output is correct
22 Correct 360 ms 84660 KB Output is correct
23 Correct 351 ms 78492 KB Output is correct
24 Correct 364 ms 78680 KB Output is correct
25 Correct 387 ms 85828 KB Output is correct
26 Correct 430 ms 81424 KB Output is correct
27 Correct 404 ms 81748 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26440 KB Output is correct
2 Correct 37 ms 28872 KB Output is correct
3 Correct 39 ms 29140 KB Output is correct
4 Correct 39 ms 29124 KB Output is correct
5 Correct 47 ms 29780 KB Output is correct
6 Correct 36 ms 29128 KB Output is correct
7 Correct 28 ms 26060 KB Output is correct
8 Correct 348 ms 87404 KB Output is correct
9 Correct 321 ms 87300 KB Output is correct
10 Correct 27 ms 26544 KB Output is correct
11 Correct 396 ms 90580 KB Output is correct
12 Correct 389 ms 90632 KB Output is correct
13 Correct 323 ms 95824 KB Output is correct
14 Correct 29 ms 26196 KB Output is correct
15 Correct 317 ms 82380 KB Output is correct
16 Correct 347 ms 77396 KB Output is correct
17 Correct 368 ms 77232 KB Output is correct
18 Correct 392 ms 77652 KB Output is correct
19 Correct 538 ms 88568 KB Output is correct
20 Correct 541 ms 87256 KB Output is correct
21 Correct 336 ms 84596 KB Output is correct
22 Correct 360 ms 84660 KB Output is correct
23 Correct 351 ms 78492 KB Output is correct
24 Correct 364 ms 78680 KB Output is correct
25 Correct 387 ms 85828 KB Output is correct
26 Correct 430 ms 81424 KB Output is correct
27 Correct 404 ms 81748 KB Output is correct
28 Correct 35 ms 29248 KB Output is correct
29 Correct 465 ms 206048 KB Output is correct
30 Correct 359 ms 177576 KB Output is correct
31 Correct 417 ms 166040 KB Output is correct
32 Correct 588 ms 309408 KB Output is correct
33 Correct 445 ms 290460 KB Output is correct
34 Correct 34 ms 29376 KB Output is correct
35 Correct 880 ms 146664 KB Output is correct
36 Correct 1412 ms 341664 KB Output is correct
37 Correct 1380 ms 342476 KB Output is correct
38 Correct 33 ms 29140 KB Output is correct
39 Correct 1146 ms 258120 KB Output is correct
40 Correct 1106 ms 263564 KB Output is correct
41 Correct 1615 ms 410848 KB Output is correct
42 Correct 1621 ms 411036 KB Output is correct
43 Correct 40 ms 28868 KB Output is correct
44 Correct 941 ms 297640 KB Output is correct
45 Correct 1024 ms 235120 KB Output is correct
46 Correct 1545 ms 383344 KB Output is correct
47 Correct 1234 ms 234360 KB Output is correct
48 Correct 1746 ms 347784 KB Output is correct
49 Correct 2737 ms 267072 KB Output is correct
50 Correct 1409 ms 121032 KB Output is correct
51 Correct 1264 ms 389880 KB Output is correct
52 Correct 1437 ms 345672 KB Output is correct
53 Correct 1381 ms 345784 KB Output is correct
54 Correct 1384 ms 345844 KB Output is correct
55 Correct 1074 ms 328016 KB Output is correct
56 Correct 681 ms 240692 KB Output is correct
57 Correct 1275 ms 344436 KB Output is correct
58 Correct 1416 ms 293932 KB Output is correct
59 Correct 545 ms 114260 KB Output is correct