oj.uz

Submission #912755

# Submission time Handle Problem Language Result Execution time Memory
912755 2024-01-19T20:20:58 Z MinaRagy06 Inside information (BOI21_servers) C++17
60 / 100
 3190 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 = 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], sz[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++;
	sz[i] = 1;
	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);
		sz[i] += sz[nxt];
		lca.a[curt][0] = {h, i};
		curt++;
	}
	en[i] = curt - 1;
	euleren[i] = eulert - 1;
}
vector<array<int, 4>> ask[N];
int ans[2 * N];
struct sqrt_decomp {
	int a[2 * N];
	int n;
	void init(int _n, int _v) {
		n = _n;
		for (int i = 0; i < n; i++) {
			a[i] = _v;
		}
	}
	void set(int l, int r, int v) {
		for (int i = l; i <= r; i++) {
			a[i] = v;
		}
	}
	int get(int i) {
		return a[i];
	}
} Inc, Dec;
set<int> activeinc, activedec;
bool ininc[N], indec[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 [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;
	}
	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;
	pair<char, vector<int>> v[q];
	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);
			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});
		} 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 if (isanc(a, x)) {
					ask[a].push_back({x, a, t - 1, i});
				} else {
					int mid = lca.query(a, x);
					ask[mid].push_back({x, a, t - 1, i});
				}
			}
		}
	}
	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 25024 KB Output is correct
2 Correct 40 ms 27592 KB Output is correct
3 Correct 40 ms 27904 KB Output is correct
4 Correct 45 ms 27848 KB Output is correct
5 Correct 54 ms 28756 KB Output is correct
6 Correct 39 ms 27692 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 25024 KB Output is correct
2 Correct 40 ms 27592 KB Output is correct
3 Correct 40 ms 27904 KB Output is correct
4 Correct 45 ms 27848 KB Output is correct
5 Correct 54 ms 28756 KB Output is correct
6 Correct 39 ms 27692 KB Output is correct
7 Correct 39 ms 33204 KB Output is correct
8 Correct 499 ms 352036 KB Output is correct
9 Correct 324 ms 319096 KB Output is correct
10 Correct 469 ms 297952 KB Output is correct
11 Runtime error 596 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24516 KB Output is correct
2 Correct 368 ms 89856 KB Output is correct
3 Correct 358 ms 89936 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24516 KB Output is correct
2 Correct 368 ms 89856 KB Output is correct
3 Correct 358 ms 89936 KB Output is correct
4 Correct 36 ms 31164 KB Output is correct
5 Correct 1277 ms 214104 KB Output is correct
6 Runtime error 602 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 31 ms 25180 KB Output is correct
2 Correct 2218 ms 89084 KB Output is correct
3 Correct 2228 ms 89044 KB Output is correct
4 Correct 2020 ms 94600 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25180 KB Output is correct
2 Correct 2218 ms 89084 KB Output is correct
3 Correct 2228 ms 89044 KB Output is correct
4 Correct 2020 ms 94600 KB Output is correct
5 Correct 37 ms 29712 KB Output is correct
6 Correct 2838 ms 420156 KB Output is correct
7 Correct 3138 ms 420208 KB Output is correct
8 Runtime error 736 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 24772 KB Output is correct
2 Correct 341 ms 84728 KB Output is correct
3 Correct 393 ms 79536 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 24772 KB Output is correct
2 Correct 341 ms 84728 KB Output is correct
3 Correct 393 ms 79536 KB Output is correct
4 Correct 38 ms 30892 KB Output is correct
5 Correct 1008 ms 493924 KB Output is correct
6 Correct 1159 ms 382152 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25284 KB Output is correct
2 Correct 2225 ms 89212 KB Output is correct
3 Correct 2318 ms 89236 KB Output is correct
4 Correct 2148 ms 94492 KB Output is correct
5 Correct 35 ms 24776 KB Output is correct
6 Correct 347 ms 84540 KB Output is correct
7 Correct 398 ms 79528 KB Output is correct
8 Correct 391 ms 79696 KB Output is correct
9 Correct 473 ms 80488 KB Output is correct
10 Correct 1140 ms 89576 KB Output is correct
11 Correct 1053 ms 88584 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25284 KB Output is correct
2 Correct 2225 ms 89212 KB Output is correct
3 Correct 2318 ms 89236 KB Output is correct
4 Correct 2148 ms 94492 KB Output is correct
5 Correct 35 ms 24776 KB Output is correct
6 Correct 347 ms 84540 KB Output is correct
7 Correct 398 ms 79528 KB Output is correct
8 Correct 391 ms 79696 KB Output is correct
9 Correct 473 ms 80488 KB Output is correct
10 Correct 1140 ms 89576 KB Output is correct
11 Correct 1053 ms 88584 KB Output is correct
12 Correct 36 ms 29532 KB Output is correct
13 Correct 2966 ms 420348 KB Output is correct
14 Correct 3190 ms 420028 KB Output is correct
15 Runtime error 878 ms 524288 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25012 KB Output is correct
2 Correct 44 ms 27592 KB Output is correct
3 Correct 40 ms 27968 KB Output is correct
4 Correct 42 ms 27844 KB Output is correct
5 Correct 43 ms 28828 KB Output is correct
6 Correct 38 ms 27636 KB Output is correct
7 Correct 29 ms 24520 KB Output is correct
8 Correct 358 ms 89748 KB Output is correct
9 Correct 473 ms 89736 KB Output is correct
10 Correct 40 ms 25124 KB Output is correct
11 Correct 2287 ms 89060 KB Output is correct
12 Correct 2324 ms 89064 KB Output is correct
13 Correct 2041 ms 94420 KB Output is correct
14 Correct 31 ms 24784 KB Output is correct
15 Correct 375 ms 84536 KB Output is correct
16 Correct 441 ms 79704 KB Output is correct
17 Correct 379 ms 79696 KB Output is correct
18 Correct 419 ms 80252 KB Output is correct
19 Correct 1187 ms 89440 KB Output is correct
20 Correct 1076 ms 88352 KB Output is correct
21 Correct 403 ms 87052 KB Output is correct
22 Correct 466 ms 87284 KB Output is correct
23 Correct 416 ms 81272 KB Output is correct
24 Correct 366 ms 81360 KB Output is correct
25 Correct 1223 ms 87052 KB Output is correct
26 Correct 440 ms 83840 KB Output is correct
27 Correct 415 ms 84808 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25012 KB Output is correct
2 Correct 44 ms 27592 KB Output is correct
3 Correct 40 ms 27968 KB Output is correct
4 Correct 42 ms 27844 KB Output is correct
5 Correct 43 ms 28828 KB Output is correct
6 Correct 38 ms 27636 KB Output is correct
7 Correct 29 ms 24520 KB Output is correct
8 Correct 358 ms 89748 KB Output is correct
9 Correct 473 ms 89736 KB Output is correct
10 Correct 40 ms 25124 KB Output is correct
11 Correct 2287 ms 89060 KB Output is correct
12 Correct 2324 ms 89064 KB Output is correct
13 Correct 2041 ms 94420 KB Output is correct
14 Correct 31 ms 24784 KB Output is correct
15 Correct 375 ms 84536 KB Output is correct
16 Correct 441 ms 79704 KB Output is correct
17 Correct 379 ms 79696 KB Output is correct
18 Correct 419 ms 80252 KB Output is correct
19 Correct 1187 ms 89440 KB Output is correct
20 Correct 1076 ms 88352 KB Output is correct
21 Correct 403 ms 87052 KB Output is correct
22 Correct 466 ms 87284 KB Output is correct
23 Correct 416 ms 81272 KB Output is correct
24 Correct 366 ms 81360 KB Output is correct
25 Correct 1223 ms 87052 KB Output is correct
26 Correct 440 ms 83840 KB Output is correct
27 Correct 415 ms 84808 KB Output is correct
28 Correct 38 ms 32184 KB Output is correct
29 Correct 520 ms 350048 KB Output is correct
30 Correct 309 ms 318748 KB Output is correct
31 Correct 453 ms 296332 KB Output is correct
32 Runtime error 599 ms 524288 KB Execution killed with signal 9
33 Halted 0 ms 0 KB -