oj.uz

Submission #912754

# Submission time Handle Problem Language Result Execution time Memory
912754 2024-01-19T20:19:29 Z MinaRagy06 Inside information (BOI21_servers) C++17
60 / 100
 2285 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 = 700, 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 26044 KB Output is correct
2 Correct 49 ms 29124 KB Output is correct
3 Correct 48 ms 29412 KB Output is correct
4 Correct 43 ms 29392 KB Output is correct
5 Correct 44 ms 30036 KB Output is correct
6 Correct 39 ms 28868 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 26044 KB Output is correct
2 Correct 49 ms 29124 KB Output is correct
3 Correct 48 ms 29412 KB Output is correct
4 Correct 43 ms 29392 KB Output is correct
5 Correct 44 ms 30036 KB Output is correct
6 Correct 39 ms 28868 KB Output is correct
7 Correct 39 ms 32164 KB Output is correct
8 Correct 660 ms 384280 KB Output is correct
9 Correct 471 ms 521984 KB Output is correct
10 Correct 669 ms 462172 KB Output is correct
11 Runtime error 616 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 33 ms 25500 KB Output is correct
2 Correct 321 ms 92668 KB Output is correct
3 Correct 325 ms 92620 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 25500 KB Output is correct
2 Correct 321 ms 92668 KB Output is correct
3 Correct 325 ms 92620 KB Output is correct
4 Correct 36 ms 32700 KB Output is correct
5 Correct 940 ms 349260 KB Output is correct
6 Runtime error 433 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 26140 KB Output is correct
2 Correct 2161 ms 92356 KB Output is correct
3 Correct 2285 ms 92592 KB Output is correct
4 Correct 1989 ms 97800 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 26140 KB Output is correct
2 Correct 2161 ms 92356 KB Output is correct
3 Correct 2285 ms 92592 KB Output is correct
4 Correct 1989 ms 97800 KB Output is correct
5 Correct 37 ms 30476 KB Output is correct
6 Runtime error 793 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 25540 KB Output is correct
2 Correct 304 ms 87948 KB Output is correct
3 Correct 343 ms 83032 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 25540 KB Output is correct
2 Correct 304 ms 87948 KB Output is correct
3 Correct 343 ms 83032 KB Output is correct
4 Correct 37 ms 30896 KB Output is correct
5 Correct 868 ms 500688 KB Output is correct
6 Correct 1314 ms 524288 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 26192 KB Output is correct
2 Correct 2220 ms 92564 KB Output is correct
3 Correct 2178 ms 92360 KB Output is correct
4 Correct 1978 ms 97892 KB Output is correct
5 Correct 31 ms 25548 KB Output is correct
6 Correct 294 ms 87992 KB Output is correct
7 Correct 334 ms 83028 KB Output is correct
8 Correct 351 ms 83016 KB Output is correct
9 Correct 376 ms 83556 KB Output is correct
10 Correct 989 ms 93092 KB Output is correct
11 Correct 954 ms 91764 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 26192 KB Output is correct
2 Correct 2220 ms 92564 KB Output is correct
3 Correct 2178 ms 92360 KB Output is correct
4 Correct 1978 ms 97892 KB Output is correct
5 Correct 31 ms 25548 KB Output is correct
6 Correct 294 ms 87992 KB Output is correct
7 Correct 334 ms 83028 KB Output is correct
8 Correct 351 ms 83016 KB Output is correct
9 Correct 376 ms 83556 KB Output is correct
10 Correct 989 ms 93092 KB Output is correct
11 Correct 954 ms 91764 KB Output is correct
12 Correct 36 ms 30488 KB Output is correct
13 Runtime error 790 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 26048 KB Output is correct
2 Correct 41 ms 29080 KB Output is correct
3 Correct 45 ms 29448 KB Output is correct
4 Correct 44 ms 29380 KB Output is correct
5 Correct 45 ms 30044 KB Output is correct
6 Correct 39 ms 28872 KB Output is correct
7 Correct 30 ms 25420 KB Output is correct
8 Correct 320 ms 92668 KB Output is correct
9 Correct 318 ms 92580 KB Output is correct
10 Correct 31 ms 26204 KB Output is correct
11 Correct 2168 ms 92532 KB Output is correct
12 Correct 2185 ms 92368 KB Output is correct
13 Correct 2013 ms 97900 KB Output is correct
14 Correct 31 ms 25764 KB Output is correct
15 Correct 286 ms 87868 KB Output is correct
16 Correct 367 ms 83220 KB Output is correct
17 Correct 373 ms 82944 KB Output is correct
18 Correct 392 ms 83396 KB Output is correct
19 Correct 986 ms 93028 KB Output is correct
20 Correct 991 ms 91600 KB Output is correct
21 Correct 348 ms 90332 KB Output is correct
22 Correct 335 ms 90252 KB Output is correct
23 Correct 353 ms 84440 KB Output is correct
24 Correct 353 ms 84548 KB Output is correct
25 Correct 1139 ms 90956 KB Output is correct
26 Correct 384 ms 87376 KB Output is correct
27 Correct 371 ms 88432 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 26048 KB Output is correct
2 Correct 41 ms 29080 KB Output is correct
3 Correct 45 ms 29448 KB Output is correct
4 Correct 44 ms 29380 KB Output is correct
5 Correct 45 ms 30044 KB Output is correct
6 Correct 39 ms 28872 KB Output is correct
7 Correct 30 ms 25420 KB Output is correct
8 Correct 320 ms 92668 KB Output is correct
9 Correct 318 ms 92580 KB Output is correct
10 Correct 31 ms 26204 KB Output is correct
11 Correct 2168 ms 92532 KB Output is correct
12 Correct 2185 ms 92368 KB Output is correct
13 Correct 2013 ms 97900 KB Output is correct
14 Correct 31 ms 25764 KB Output is correct
15 Correct 286 ms 87868 KB Output is correct
16 Correct 367 ms 83220 KB Output is correct
17 Correct 373 ms 82944 KB Output is correct
18 Correct 392 ms 83396 KB Output is correct
19 Correct 986 ms 93028 KB Output is correct
20 Correct 991 ms 91600 KB Output is correct
21 Correct 348 ms 90332 KB Output is correct
22 Correct 335 ms 90252 KB Output is correct
23 Correct 353 ms 84440 KB Output is correct
24 Correct 353 ms 84548 KB Output is correct
25 Correct 1139 ms 90956 KB Output is correct
26 Correct 384 ms 87376 KB Output is correct
27 Correct 371 ms 88432 KB Output is correct
28 Correct 41 ms 33264 KB Output is correct
29 Correct 640 ms 385928 KB Output is correct
30 Correct 496 ms 520956 KB Output is correct
31 Correct 648 ms 462200 KB Output is correct
32 Runtime error 664 ms 524288 KB Execution killed with signal 9
33 Halted 0 ms 0 KB -