oj.uz

Submission #912802

# Submission time Handle Problem Language Result Execution time Memory
912802 2024-01-19T23:42:44 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 348640 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 = 400, 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 29 ms 26440 KB Output is correct
2 Correct 42 ms 28876 KB Output is correct
3 Correct 46 ms 29132 KB Output is correct
4 Correct 47 ms 29128 KB Output is correct
5 Correct 43 ms 29804 KB Output is correct
6 Correct 40 ms 28972 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26440 KB Output is correct
2 Correct 42 ms 28876 KB Output is correct
3 Correct 46 ms 29132 KB Output is correct
4 Correct 47 ms 29128 KB Output is correct
5 Correct 43 ms 29804 KB Output is correct
6 Correct 40 ms 28972 KB Output is correct
7 Correct 46 ms 29104 KB Output is correct
8 Correct 434 ms 150048 KB Output is correct
9 Correct 294 ms 175396 KB Output is correct
10 Correct 403 ms 139416 KB Output is correct
11 Correct 522 ms 252160 KB Output is correct
12 Correct 413 ms 291572 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 353 ms 87300 KB Output is correct
3 Correct 388 ms 87300 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 353 ms 87300 KB Output is correct
3 Correct 388 ms 87300 KB Output is correct
4 Correct 42 ms 30656 KB Output is correct
5 Correct 1882 ms 147484 KB Output is correct
6 Correct 2235 ms 343556 KB Output is correct
7 Correct 1562 ms 343296 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26448 KB Output is correct
2 Correct 471 ms 90644 KB Output is correct
3 Correct 449 ms 90632 KB Output is correct
4 Correct 386 ms 95852 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26448 KB Output is correct
2 Correct 471 ms 90644 KB Output is correct
3 Correct 449 ms 90632 KB Output is correct
4 Correct 386 ms 95852 KB Output is correct
5 Correct 38 ms 29140 KB Output is correct
6 Correct 1534 ms 225444 KB Output is correct
7 Correct 1353 ms 229160 KB Output is correct
8 Correct 1859 ms 347932 KB Output is correct
9 Correct 1885 ms 348544 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26136 KB Output is correct
2 Correct 415 ms 82400 KB Output is correct
3 Correct 523 ms 77392 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26136 KB Output is correct
2 Correct 415 ms 82400 KB Output is correct
3 Correct 523 ms 77392 KB Output is correct
4 Correct 36 ms 28872 KB Output is correct
5 Correct 892 ms 288600 KB Output is correct
6 Correct 1136 ms 196736 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26472 KB Output is correct
2 Correct 424 ms 90804 KB Output is correct
3 Correct 484 ms 90884 KB Output is correct
4 Correct 465 ms 96056 KB Output is correct
5 Correct 29 ms 26236 KB Output is correct
6 Correct 340 ms 82280 KB Output is correct
7 Correct 475 ms 77396 KB Output is correct
8 Correct 360 ms 77320 KB Output is correct
9 Correct 477 ms 77652 KB Output is correct
10 Correct 669 ms 88556 KB Output is correct
11 Correct 671 ms 87236 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26472 KB Output is correct
2 Correct 424 ms 90804 KB Output is correct
3 Correct 484 ms 90884 KB Output is correct
4 Correct 465 ms 96056 KB Output is correct
5 Correct 29 ms 26236 KB Output is correct
6 Correct 340 ms 82280 KB Output is correct
7 Correct 475 ms 77396 KB Output is correct
8 Correct 360 ms 77320 KB Output is correct
9 Correct 477 ms 77652 KB Output is correct
10 Correct 669 ms 88556 KB Output is correct
11 Correct 671 ms 87236 KB Output is correct
12 Correct 40 ms 29136 KB Output is correct
13 Correct 1219 ms 225540 KB Output is correct
14 Correct 1431 ms 229028 KB Output is correct
15 Correct 1958 ms 348196 KB Output is correct
16 Correct 2055 ms 348384 KB Output is correct
17 Correct 36 ms 28864 KB Output is correct
18 Correct 1127 ms 288500 KB Output is correct
19 Correct 1192 ms 197032 KB Output is correct
20 Correct 1647 ms 305496 KB Output is correct
21 Correct 1301 ms 224548 KB Output is correct
22 Correct 2360 ms 308836 KB Output is correct
23 Execution timed out 3510 ms 175044 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 26440 KB Output is correct
2 Correct 53 ms 28876 KB Output is correct
3 Correct 60 ms 29132 KB Output is correct
4 Correct 60 ms 29124 KB Output is correct
5 Correct 69 ms 29772 KB Output is correct
6 Correct 58 ms 29036 KB Output is correct
7 Correct 37 ms 26100 KB Output is correct
8 Correct 402 ms 87456 KB Output is correct
9 Correct 435 ms 87592 KB Output is correct
10 Correct 29 ms 26544 KB Output is correct
11 Correct 458 ms 90876 KB Output is correct
12 Correct 564 ms 90828 KB Output is correct
13 Correct 353 ms 96076 KB Output is correct
14 Correct 30 ms 26104 KB Output is correct
15 Correct 399 ms 82280 KB Output is correct
16 Correct 421 ms 77196 KB Output is correct
17 Correct 522 ms 77232 KB Output is correct
18 Correct 514 ms 77680 KB Output is correct
19 Correct 580 ms 88588 KB Output is correct
20 Correct 550 ms 87244 KB Output is correct
21 Correct 479 ms 84564 KB Output is correct
22 Correct 526 ms 84536 KB Output is correct
23 Correct 366 ms 78616 KB Output is correct
24 Correct 484 ms 78784 KB Output is correct
25 Correct 484 ms 85808 KB Output is correct
26 Correct 579 ms 81284 KB Output is correct
27 Correct 481 ms 81888 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 26440 KB Output is correct
2 Correct 53 ms 28876 KB Output is correct
3 Correct 60 ms 29132 KB Output is correct
4 Correct 60 ms 29124 KB Output is correct
5 Correct 69 ms 29772 KB Output is correct
6 Correct 58 ms 29036 KB Output is correct
7 Correct 37 ms 26100 KB Output is correct
8 Correct 402 ms 87456 KB Output is correct
9 Correct 435 ms 87592 KB Output is correct
10 Correct 29 ms 26544 KB Output is correct
11 Correct 458 ms 90876 KB Output is correct
12 Correct 564 ms 90828 KB Output is correct
13 Correct 353 ms 96076 KB Output is correct
14 Correct 30 ms 26104 KB Output is correct
15 Correct 399 ms 82280 KB Output is correct
16 Correct 421 ms 77196 KB Output is correct
17 Correct 522 ms 77232 KB Output is correct
18 Correct 514 ms 77680 KB Output is correct
19 Correct 580 ms 88588 KB Output is correct
20 Correct 550 ms 87244 KB Output is correct
21 Correct 479 ms 84564 KB Output is correct
22 Correct 526 ms 84536 KB Output is correct
23 Correct 366 ms 78616 KB Output is correct
24 Correct 484 ms 78784 KB Output is correct
25 Correct 484 ms 85808 KB Output is correct
26 Correct 579 ms 81284 KB Output is correct
27 Correct 481 ms 81888 KB Output is correct
28 Correct 37 ms 29240 KB Output is correct
29 Correct 395 ms 155000 KB Output is correct
30 Correct 291 ms 176080 KB Output is correct
31 Correct 429 ms 138628 KB Output is correct
32 Correct 599 ms 252192 KB Output is correct
33 Correct 400 ms 291676 KB Output is correct
34 Correct 37 ms 29128 KB Output is correct
35 Correct 1102 ms 148192 KB Output is correct
36 Correct 2399 ms 343324 KB Output is correct
37 Correct 1853 ms 342992 KB Output is correct
38 Correct 47 ms 28924 KB Output is correct
39 Correct 1281 ms 225444 KB Output is correct
40 Correct 1293 ms 229412 KB Output is correct
41 Correct 1828 ms 348200 KB Output is correct
42 Correct 1850 ms 348640 KB Output is correct
43 Correct 40 ms 28820 KB Output is correct
44 Correct 937 ms 289824 KB Output is correct
45 Correct 1352 ms 195332 KB Output is correct
46 Correct 1710 ms 306960 KB Output is correct
47 Correct 1417 ms 221008 KB Output is correct
48 Correct 1916 ms 308184 KB Output is correct
49 Execution timed out 3572 ms 174604 KB Time limit exceeded
50 Halted 0 ms 0 KB -