oj.uz

Submission #912756

# Submission time Handle Problem Language Result Execution time Memory
912756 2024-01-19T20:21:30 Z MinaRagy06 Inside information (BOI21_servers) C++17
65 / 100
 3500 ms 347612 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 = 200, 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 31 ms 25012 KB Output is correct
2 Correct 40 ms 27624 KB Output is correct
3 Correct 39 ms 27968 KB Output is correct
4 Correct 45 ms 27844 KB Output is correct
5 Correct 52 ms 28740 KB Output is correct
6 Correct 38 ms 27528 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25012 KB Output is correct
2 Correct 40 ms 27624 KB Output is correct
3 Correct 39 ms 27968 KB Output is correct
4 Correct 45 ms 27844 KB Output is correct
5 Correct 52 ms 28740 KB Output is correct
6 Correct 38 ms 27528 KB Output is correct
7 Correct 43 ms 32948 KB Output is correct
8 Correct 263 ms 146292 KB Output is correct
9 Correct 165 ms 164648 KB Output is correct
10 Correct 224 ms 136248 KB Output is correct
11 Correct 333 ms 250068 KB Output is correct
12 Correct 194 ms 290956 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 24668 KB Output is correct
2 Correct 499 ms 89640 KB Output is correct
3 Correct 541 ms 90004 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 24668 KB Output is correct
2 Correct 499 ms 89640 KB Output is correct
3 Correct 541 ms 90004 KB Output is correct
4 Correct 48 ms 32188 KB Output is correct
5 Correct 2565 ms 148884 KB Output is correct
6 Correct 2216 ms 346688 KB Output is correct
7 Correct 2589 ms 346228 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 25176 KB Output is correct
2 Correct 2702 ms 89048 KB Output is correct
3 Correct 2616 ms 89560 KB Output is correct
4 Correct 2205 ms 94668 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 25176 KB Output is correct
2 Correct 2702 ms 89048 KB Output is correct
3 Correct 2616 ms 89560 KB Output is correct
4 Correct 2205 ms 94668 KB Output is correct
5 Correct 37 ms 29720 KB Output is correct
6 Correct 2696 ms 222588 KB Output is correct
7 Execution timed out 3567 ms 225732 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24776 KB Output is correct
2 Correct 509 ms 84756 KB Output is correct
3 Correct 552 ms 79560 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24776 KB Output is correct
2 Correct 509 ms 84756 KB Output is correct
3 Correct 552 ms 79560 KB Output is correct
4 Correct 37 ms 29888 KB Output is correct
5 Correct 1157 ms 289760 KB Output is correct
6 Correct 969 ms 194544 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25172 KB Output is correct
2 Correct 2462 ms 89056 KB Output is correct
3 Correct 2423 ms 89296 KB Output is correct
4 Correct 2347 ms 94612 KB Output is correct
5 Correct 34 ms 24788 KB Output is correct
6 Correct 472 ms 84540 KB Output is correct
7 Correct 507 ms 79756 KB Output is correct
8 Correct 543 ms 79520 KB Output is correct
9 Correct 560 ms 80140 KB Output is correct
10 Correct 1390 ms 89788 KB Output is correct
11 Correct 1353 ms 88348 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25172 KB Output is correct
2 Correct 2462 ms 89056 KB Output is correct
3 Correct 2423 ms 89296 KB Output is correct
4 Correct 2347 ms 94612 KB Output is correct
5 Correct 34 ms 24788 KB Output is correct
6 Correct 472 ms 84540 KB Output is correct
7 Correct 507 ms 79756 KB Output is correct
8 Correct 543 ms 79520 KB Output is correct
9 Correct 560 ms 80140 KB Output is correct
10 Correct 1390 ms 89788 KB Output is correct
11 Correct 1353 ms 88348 KB Output is correct
12 Correct 37 ms 29708 KB Output is correct
13 Correct 2629 ms 222616 KB Output is correct
14 Correct 3469 ms 226332 KB Output is correct
15 Correct 2841 ms 347024 KB Output is correct
16 Correct 2855 ms 347588 KB Output is correct
17 Correct 38 ms 30840 KB Output is correct
18 Correct 994 ms 292008 KB Output is correct
19 Correct 945 ms 196748 KB Output is correct
20 Correct 1108 ms 299616 KB Output is correct
21 Correct 980 ms 227652 KB Output is correct
22 Correct 2337 ms 312308 KB Output is correct
23 Execution timed out 3552 ms 178488 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25024 KB Output is correct
2 Correct 41 ms 27592 KB Output is correct
3 Correct 41 ms 27968 KB Output is correct
4 Correct 44 ms 27848 KB Output is correct
5 Correct 43 ms 28760 KB Output is correct
6 Correct 43 ms 27924 KB Output is correct
7 Correct 33 ms 24696 KB Output is correct
8 Correct 493 ms 89848 KB Output is correct
9 Correct 497 ms 89712 KB Output is correct
10 Correct 31 ms 25176 KB Output is correct
11 Correct 2368 ms 89040 KB Output is correct
12 Correct 2371 ms 89504 KB Output is correct
13 Correct 2184 ms 95012 KB Output is correct
14 Correct 31 ms 24772 KB Output is correct
15 Correct 527 ms 84692 KB Output is correct
16 Correct 521 ms 79720 KB Output is correct
17 Correct 579 ms 79604 KB Output is correct
18 Correct 578 ms 80100 KB Output is correct
19 Correct 1383 ms 89772 KB Output is correct
20 Correct 1332 ms 88344 KB Output is correct
21 Correct 519 ms 87424 KB Output is correct
22 Correct 514 ms 87028 KB Output is correct
23 Correct 515 ms 81232 KB Output is correct
24 Correct 510 ms 81456 KB Output is correct
25 Correct 1280 ms 87212 KB Output is correct
26 Correct 670 ms 83796 KB Output is correct
27 Correct 684 ms 84792 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25024 KB Output is correct
2 Correct 41 ms 27592 KB Output is correct
3 Correct 41 ms 27968 KB Output is correct
4 Correct 44 ms 27848 KB Output is correct
5 Correct 43 ms 28760 KB Output is correct
6 Correct 43 ms 27924 KB Output is correct
7 Correct 33 ms 24696 KB Output is correct
8 Correct 493 ms 89848 KB Output is correct
9 Correct 497 ms 89712 KB Output is correct
10 Correct 31 ms 25176 KB Output is correct
11 Correct 2368 ms 89040 KB Output is correct
12 Correct 2371 ms 89504 KB Output is correct
13 Correct 2184 ms 95012 KB Output is correct
14 Correct 31 ms 24772 KB Output is correct
15 Correct 527 ms 84692 KB Output is correct
16 Correct 521 ms 79720 KB Output is correct
17 Correct 579 ms 79604 KB Output is correct
18 Correct 578 ms 80100 KB Output is correct
19 Correct 1383 ms 89772 KB Output is correct
20 Correct 1332 ms 88344 KB Output is correct
21 Correct 519 ms 87424 KB Output is correct
22 Correct 514 ms 87028 KB Output is correct
23 Correct 515 ms 81232 KB Output is correct
24 Correct 510 ms 81456 KB Output is correct
25 Correct 1280 ms 87212 KB Output is correct
26 Correct 670 ms 83796 KB Output is correct
27 Correct 684 ms 84792 KB Output is correct
28 Correct 38 ms 31424 KB Output is correct
29 Correct 212 ms 152992 KB Output is correct
30 Correct 156 ms 167308 KB Output is correct
31 Correct 211 ms 135968 KB Output is correct
32 Correct 315 ms 250340 KB Output is correct
33 Correct 188 ms 289676 KB Output is correct
34 Correct 36 ms 32444 KB Output is correct
35 Correct 2028 ms 150800 KB Output is correct
36 Correct 1978 ms 345356 KB Output is correct
37 Correct 2072 ms 346316 KB Output is correct
38 Correct 36 ms 30476 KB Output is correct
39 Correct 2704 ms 225860 KB Output is correct
40 Correct 3423 ms 229772 KB Output is correct
41 Correct 2895 ms 347308 KB Output is correct
42 Correct 2844 ms 347612 KB Output is correct
43 Correct 37 ms 31688 KB Output is correct
44 Correct 963 ms 294388 KB Output is correct
45 Correct 919 ms 197852 KB Output is correct
46 Correct 1083 ms 298988 KB Output is correct
47 Correct 1075 ms 225172 KB Output is correct
48 Correct 2248 ms 310936 KB Output is correct
49 Execution timed out 3548 ms 178232 KB Time limit exceeded
50 Halted 0 ms 0 KB -