oj.uz

Submission #912803

# Submission time Handle Problem Language Result Execution time Memory
912803 2024-01-19T23:43:08 Z MinaRagy06 Inside information (BOI21_servers) C++17
67.5 / 100
 3500 ms 524288 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 = 600, 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 32 ms 26436 KB Output is correct
2 Correct 49 ms 28876 KB Output is correct
3 Correct 38 ms 29108 KB Output is correct
4 Correct 42 ms 29132 KB Output is correct
5 Correct 47 ms 29780 KB Output is correct
6 Correct 41 ms 29004 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 26436 KB Output is correct
2 Correct 49 ms 28876 KB Output is correct
3 Correct 38 ms 29108 KB Output is correct
4 Correct 42 ms 29132 KB Output is correct
5 Correct 47 ms 29780 KB Output is correct
6 Correct 41 ms 29004 KB Output is correct
7 Correct 48 ms 29240 KB Output is correct
8 Correct 560 ms 215940 KB Output is correct
9 Correct 393 ms 188632 KB Output is correct
10 Correct 636 ms 249492 KB Output is correct
11 Correct 531 ms 254176 KB Output is correct
12 Correct 441 ms 291304 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26320 KB Output is correct
2 Correct 406 ms 87540 KB Output is correct
3 Correct 393 ms 87512 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26320 KB Output is correct
2 Correct 406 ms 87540 KB Output is correct
3 Correct 393 ms 87512 KB Output is correct
4 Correct 43 ms 30332 KB Output is correct
5 Correct 1565 ms 150260 KB Output is correct
6 Runtime error 1644 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 26452 KB Output is correct
2 Correct 508 ms 90628 KB Output is correct
3 Correct 427 ms 90656 KB Output is correct
4 Correct 316 ms 95880 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 26452 KB Output is correct
2 Correct 508 ms 90628 KB Output is correct
3 Correct 427 ms 90656 KB Output is correct
4 Correct 316 ms 95880 KB Output is correct
5 Correct 34 ms 28988 KB Output is correct
6 Correct 1611 ms 292152 KB Output is correct
7 Correct 1329 ms 298860 KB Output is correct
8 Correct 2395 ms 470300 KB Output is correct
9 Correct 2499 ms 470996 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 26192 KB Output is correct
2 Correct 412 ms 82252 KB Output is correct
3 Correct 434 ms 77216 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 26192 KB Output is correct
2 Correct 412 ms 82252 KB Output is correct
3 Correct 434 ms 77216 KB Output is correct
4 Correct 45 ms 28920 KB Output is correct
5 Correct 1215 ms 321968 KB Output is correct
6 Correct 1353 ms 308860 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26548 KB Output is correct
2 Correct 402 ms 90820 KB Output is correct
3 Correct 465 ms 90832 KB Output is correct
4 Correct 388 ms 95876 KB Output is correct
5 Correct 39 ms 26252 KB Output is correct
6 Correct 338 ms 82444 KB Output is correct
7 Correct 415 ms 77392 KB Output is correct
8 Correct 427 ms 77140 KB Output is correct
9 Correct 480 ms 77852 KB Output is correct
10 Correct 673 ms 88752 KB Output is correct
11 Correct 580 ms 87348 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26548 KB Output is correct
2 Correct 402 ms 90820 KB Output is correct
3 Correct 465 ms 90832 KB Output is correct
4 Correct 388 ms 95876 KB Output is correct
5 Correct 39 ms 26252 KB Output is correct
6 Correct 338 ms 82444 KB Output is correct
7 Correct 415 ms 77392 KB Output is correct
8 Correct 427 ms 77140 KB Output is correct
9 Correct 480 ms 77852 KB Output is correct
10 Correct 673 ms 88752 KB Output is correct
11 Correct 580 ms 87348 KB Output is correct
12 Correct 35 ms 29144 KB Output is correct
13 Correct 1668 ms 292296 KB Output is correct
14 Correct 1273 ms 298880 KB Output is correct
15 Correct 2631 ms 470304 KB Output is correct
16 Correct 2589 ms 471244 KB Output is correct
17 Correct 35 ms 28888 KB Output is correct
18 Correct 1467 ms 325532 KB Output is correct
19 Correct 1537 ms 309876 KB Output is correct
20 Correct 2052 ms 456964 KB Output is correct
21 Correct 1565 ms 249408 KB Output is correct
22 Correct 2635 ms 398976 KB Output is correct
23 Execution timed out 3515 ms 267936 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26448 KB Output is correct
2 Correct 38 ms 28720 KB Output is correct
3 Correct 42 ms 29136 KB Output is correct
4 Correct 44 ms 29384 KB Output is correct
5 Correct 38 ms 29780 KB Output is correct
6 Correct 50 ms 29124 KB Output is correct
7 Correct 40 ms 26064 KB Output is correct
8 Correct 311 ms 87556 KB Output is correct
9 Correct 318 ms 87484 KB Output is correct
10 Correct 28 ms 26460 KB Output is correct
11 Correct 484 ms 90964 KB Output is correct
12 Correct 475 ms 90832 KB Output is correct
13 Correct 359 ms 95996 KB Output is correct
14 Correct 29 ms 26324 KB Output is correct
15 Correct 387 ms 82440 KB Output is correct
16 Correct 342 ms 77224 KB Output is correct
17 Correct 443 ms 77284 KB Output is correct
18 Correct 475 ms 77648 KB Output is correct
19 Correct 608 ms 88696 KB Output is correct
20 Correct 563 ms 87244 KB Output is correct
21 Correct 390 ms 84572 KB Output is correct
22 Correct 351 ms 84524 KB Output is correct
23 Correct 436 ms 78440 KB Output is correct
24 Correct 448 ms 78736 KB Output is correct
25 Correct 418 ms 85908 KB Output is correct
26 Correct 530 ms 81332 KB Output is correct
27 Correct 454 ms 81792 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26448 KB Output is correct
2 Correct 38 ms 28720 KB Output is correct
3 Correct 42 ms 29136 KB Output is correct
4 Correct 44 ms 29384 KB Output is correct
5 Correct 38 ms 29780 KB Output is correct
6 Correct 50 ms 29124 KB Output is correct
7 Correct 40 ms 26064 KB Output is correct
8 Correct 311 ms 87556 KB Output is correct
9 Correct 318 ms 87484 KB Output is correct
10 Correct 28 ms 26460 KB Output is correct
11 Correct 484 ms 90964 KB Output is correct
12 Correct 475 ms 90832 KB Output is correct
13 Correct 359 ms 95996 KB Output is correct
14 Correct 29 ms 26324 KB Output is correct
15 Correct 387 ms 82440 KB Output is correct
16 Correct 342 ms 77224 KB Output is correct
17 Correct 443 ms 77284 KB Output is correct
18 Correct 475 ms 77648 KB Output is correct
19 Correct 608 ms 88696 KB Output is correct
20 Correct 563 ms 87244 KB Output is correct
21 Correct 390 ms 84572 KB Output is correct
22 Correct 351 ms 84524 KB Output is correct
23 Correct 436 ms 78440 KB Output is correct
24 Correct 448 ms 78736 KB Output is correct
25 Correct 418 ms 85908 KB Output is correct
26 Correct 530 ms 81332 KB Output is correct
27 Correct 454 ms 81792 KB Output is correct
28 Correct 51 ms 29240 KB Output is correct
29 Correct 586 ms 212268 KB Output is correct
30 Correct 379 ms 189120 KB Output is correct
31 Correct 609 ms 248724 KB Output is correct
32 Correct 518 ms 254172 KB Output is correct
33 Correct 421 ms 291988 KB Output is correct
34 Correct 35 ms 29388 KB Output is correct
35 Correct 1618 ms 149752 KB Output is correct
36 Runtime error 1263 ms 524288 KB Execution killed with signal 9
37 Halted 0 ms 0 KB -