oj.uz

Submission #912771

# Submission time Handle Problem Language Result Execution time Memory
912771 2024-01-19T21:58:23 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 348112 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], 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, 4>> 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];
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;
	}
	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;
	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 33 ms 25784 KB Output is correct
2 Correct 41 ms 26280 KB Output is correct
3 Correct 40 ms 26444 KB Output is correct
4 Correct 41 ms 26456 KB Output is correct
5 Correct 41 ms 27220 KB Output is correct
6 Correct 37 ms 26052 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 25784 KB Output is correct
2 Correct 41 ms 26280 KB Output is correct
3 Correct 40 ms 26444 KB Output is correct
4 Correct 41 ms 26456 KB Output is correct
5 Correct 41 ms 27220 KB Output is correct
6 Correct 37 ms 26052 KB Output is correct
7 Correct 39 ms 33720 KB Output is correct
8 Correct 231 ms 146840 KB Output is correct
9 Correct 158 ms 164244 KB Output is correct
10 Correct 211 ms 135836 KB Output is correct
11 Correct 304 ms 247520 KB Output is correct
12 Correct 248 ms 286788 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 25292 KB Output is correct
2 Correct 470 ms 88224 KB Output is correct
3 Correct 480 ms 88480 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 25292 KB Output is correct
2 Correct 470 ms 88224 KB Output is correct
3 Correct 480 ms 88480 KB Output is correct
4 Correct 37 ms 31932 KB Output is correct
5 Correct 1815 ms 146500 KB Output is correct
6 Correct 2079 ms 343152 KB Output is correct
7 Correct 2377 ms 342576 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25936 KB Output is correct
2 Correct 547 ms 89536 KB Output is correct
3 Correct 526 ms 89904 KB Output is correct
4 Correct 445 ms 95072 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25936 KB Output is correct
2 Correct 547 ms 89536 KB Output is correct
3 Correct 526 ms 89904 KB Output is correct
4 Correct 445 ms 95072 KB Output is correct
5 Correct 36 ms 30248 KB Output is correct
6 Correct 776 ms 223136 KB Output is correct
7 Correct 1643 ms 226636 KB Output is correct
8 Correct 970 ms 347456 KB Output is correct
9 Correct 987 ms 348112 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 25408 KB Output is correct
2 Correct 465 ms 83244 KB Output is correct
3 Correct 491 ms 78420 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 25408 KB Output is correct
2 Correct 465 ms 83244 KB Output is correct
3 Correct 491 ms 78420 KB Output is correct
4 Correct 36 ms 31172 KB Output is correct
5 Correct 1018 ms 287556 KB Output is correct
6 Correct 907 ms 195220 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 25940 KB Output is correct
2 Correct 524 ms 89712 KB Output is correct
3 Correct 530 ms 89644 KB Output is correct
4 Correct 483 ms 95312 KB Output is correct
5 Correct 32 ms 25540 KB Output is correct
6 Correct 490 ms 83264 KB Output is correct
7 Correct 542 ms 78132 KB Output is correct
8 Correct 501 ms 78400 KB Output is correct
9 Correct 618 ms 78872 KB Output is correct
10 Correct 873 ms 88960 KB Output is correct
11 Correct 835 ms 87496 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 25940 KB Output is correct
2 Correct 524 ms 89712 KB Output is correct
3 Correct 530 ms 89644 KB Output is correct
4 Correct 483 ms 95312 KB Output is correct
5 Correct 32 ms 25540 KB Output is correct
6 Correct 490 ms 83264 KB Output is correct
7 Correct 542 ms 78132 KB Output is correct
8 Correct 501 ms 78400 KB Output is correct
9 Correct 618 ms 78872 KB Output is correct
10 Correct 873 ms 88960 KB Output is correct
11 Correct 835 ms 87496 KB Output is correct
12 Correct 39 ms 30220 KB Output is correct
13 Correct 897 ms 223056 KB Output is correct
14 Correct 1607 ms 226784 KB Output is correct
15 Correct 1002 ms 344928 KB Output is correct
16 Correct 992 ms 345424 KB Output is correct
17 Correct 37 ms 30576 KB Output is correct
18 Correct 955 ms 289816 KB Output is correct
19 Correct 913 ms 196764 KB Output is correct
20 Correct 1080 ms 293232 KB Output is correct
21 Correct 1045 ms 223136 KB Output is correct
22 Correct 1822 ms 307604 KB Output is correct
23 Execution timed out 3553 ms 174196 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 25788 KB Output is correct
2 Correct 40 ms 26064 KB Output is correct
3 Correct 40 ms 26436 KB Output is correct
4 Correct 43 ms 26568 KB Output is correct
5 Correct 44 ms 27732 KB Output is correct
6 Correct 38 ms 26092 KB Output is correct
7 Correct 31 ms 25240 KB Output is correct
8 Correct 478 ms 88372 KB Output is correct
9 Correct 460 ms 88496 KB Output is correct
10 Correct 31 ms 25992 KB Output is correct
11 Correct 559 ms 89652 KB Output is correct
12 Correct 545 ms 89800 KB Output is correct
13 Correct 452 ms 95028 KB Output is correct
14 Correct 31 ms 25296 KB Output is correct
15 Correct 455 ms 83236 KB Output is correct
16 Correct 511 ms 78132 KB Output is correct
17 Correct 515 ms 78148 KB Output is correct
18 Correct 546 ms 78680 KB Output is correct
19 Correct 848 ms 88748 KB Output is correct
20 Correct 829 ms 87512 KB Output is correct
21 Correct 493 ms 85396 KB Output is correct
22 Correct 508 ms 85540 KB Output is correct
23 Correct 472 ms 79696 KB Output is correct
24 Correct 489 ms 79932 KB Output is correct
25 Correct 565 ms 86124 KB Output is correct
26 Correct 666 ms 83024 KB Output is correct
27 Correct 614 ms 83012 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 25788 KB Output is correct
2 Correct 40 ms 26064 KB Output is correct
3 Correct 40 ms 26436 KB Output is correct
4 Correct 43 ms 26568 KB Output is correct
5 Correct 44 ms 27732 KB Output is correct
6 Correct 38 ms 26092 KB Output is correct
7 Correct 31 ms 25240 KB Output is correct
8 Correct 478 ms 88372 KB Output is correct
9 Correct 460 ms 88496 KB Output is correct
10 Correct 31 ms 25992 KB Output is correct
11 Correct 559 ms 89652 KB Output is correct
12 Correct 545 ms 89800 KB Output is correct
13 Correct 452 ms 95028 KB Output is correct
14 Correct 31 ms 25296 KB Output is correct
15 Correct 455 ms 83236 KB Output is correct
16 Correct 511 ms 78132 KB Output is correct
17 Correct 515 ms 78148 KB Output is correct
18 Correct 546 ms 78680 KB Output is correct
19 Correct 848 ms 88748 KB Output is correct
20 Correct 829 ms 87512 KB Output is correct
21 Correct 493 ms 85396 KB Output is correct
22 Correct 508 ms 85540 KB Output is correct
23 Correct 472 ms 79696 KB Output is correct
24 Correct 489 ms 79932 KB Output is correct
25 Correct 565 ms 86124 KB Output is correct
26 Correct 666 ms 83024 KB Output is correct
27 Correct 614 ms 83012 KB Output is correct
28 Correct 39 ms 33728 KB Output is correct
29 Correct 219 ms 144180 KB Output is correct
30 Correct 163 ms 165780 KB Output is correct
31 Correct 224 ms 134512 KB Output is correct
32 Correct 322 ms 247524 KB Output is correct
33 Correct 252 ms 288400 KB Output is correct
34 Correct 39 ms 32540 KB Output is correct
35 Correct 1674 ms 147880 KB Output is correct
36 Correct 2069 ms 343412 KB Output is correct
37 Correct 2312 ms 343956 KB Output is correct
38 Correct 38 ms 30528 KB Output is correct
39 Correct 786 ms 223176 KB Output is correct
40 Correct 1693 ms 226716 KB Output is correct
41 Correct 973 ms 344808 KB Output is correct
42 Correct 969 ms 345964 KB Output is correct
43 Correct 37 ms 30656 KB Output is correct
44 Correct 1002 ms 288992 KB Output is correct
45 Correct 879 ms 195776 KB Output is correct
46 Correct 1052 ms 296800 KB Output is correct
47 Correct 954 ms 222848 KB Output is correct
48 Correct 1771 ms 307824 KB Output is correct
49 Execution timed out 3563 ms 174812 KB Time limit exceeded
50 Halted 0 ms 0 KB -