oj.uz

Submission #912772

# Submission time Handle Problem Language Result Execution time Memory
912772 2024-01-19T22:00:12 Z MinaRagy06 Inside information (BOI21_servers) C++17
67.5 / 100
 3500 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 = 300, 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 30 ms 25792 KB Output is correct
2 Correct 39 ms 26120 KB Output is correct
3 Correct 40 ms 26436 KB Output is correct
4 Correct 47 ms 26568 KB Output is correct
5 Correct 43 ms 27472 KB Output is correct
6 Correct 38 ms 26276 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 25792 KB Output is correct
2 Correct 39 ms 26120 KB Output is correct
3 Correct 40 ms 26436 KB Output is correct
4 Correct 47 ms 26568 KB Output is correct
5 Correct 43 ms 27472 KB Output is correct
6 Correct 38 ms 26276 KB Output is correct
7 Correct 38 ms 32700 KB Output is correct
8 Correct 311 ms 229660 KB Output is correct
9 Correct 205 ms 206240 KB Output is correct
10 Correct 304 ms 245656 KB Output is correct
11 Correct 183 ms 142128 KB Output is correct
12 Correct 188 ms 156548 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25240 KB Output is correct
2 Correct 401 ms 88320 KB Output is correct
3 Correct 402 ms 88252 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25240 KB Output is correct
2 Correct 401 ms 88320 KB Output is correct
3 Correct 402 ms 88252 KB Output is correct
4 Correct 45 ms 32188 KB Output is correct
5 Correct 1387 ms 151280 KB Output is correct
6 Runtime error 1335 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 34 ms 25940 KB Output is correct
2 Correct 443 ms 89596 KB Output is correct
3 Correct 435 ms 89940 KB Output is correct
4 Correct 374 ms 95012 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 25940 KB Output is correct
2 Correct 443 ms 89596 KB Output is correct
3 Correct 435 ms 89940 KB Output is correct
4 Correct 374 ms 95012 KB Output is correct
5 Correct 39 ms 30220 KB Output is correct
6 Correct 804 ms 290568 KB Output is correct
7 Correct 1319 ms 297312 KB Output is correct
8 Correct 1032 ms 468004 KB Output is correct
9 Correct 1028 ms 468052 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25296 KB Output is correct
2 Correct 376 ms 83312 KB Output is correct
3 Correct 459 ms 78120 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25296 KB Output is correct
2 Correct 376 ms 83312 KB Output is correct
3 Correct 459 ms 78120 KB Output is correct
4 Correct 40 ms 32448 KB Output is correct
5 Correct 916 ms 313876 KB Output is correct
6 Correct 935 ms 312192 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 25936 KB Output is correct
2 Correct 466 ms 89908 KB Output is correct
3 Correct 478 ms 89684 KB Output is correct
4 Correct 376 ms 95116 KB Output is correct
5 Correct 31 ms 25308 KB Output is correct
6 Correct 381 ms 83196 KB Output is correct
7 Correct 426 ms 78280 KB Output is correct
8 Correct 454 ms 78144 KB Output is correct
9 Correct 482 ms 78864 KB Output is correct
10 Correct 683 ms 88772 KB Output is correct
11 Correct 639 ms 87708 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 25936 KB Output is correct
2 Correct 466 ms 89908 KB Output is correct
3 Correct 478 ms 89684 KB Output is correct
4 Correct 376 ms 95116 KB Output is correct
5 Correct 31 ms 25308 KB Output is correct
6 Correct 381 ms 83196 KB Output is correct
7 Correct 426 ms 78280 KB Output is correct
8 Correct 454 ms 78144 KB Output is correct
9 Correct 482 ms 78864 KB Output is correct
10 Correct 683 ms 88772 KB Output is correct
11 Correct 639 ms 87708 KB Output is correct
12 Correct 35 ms 30308 KB Output is correct
13 Correct 799 ms 290828 KB Output is correct
14 Correct 1289 ms 297352 KB Output is correct
15 Correct 1074 ms 468096 KB Output is correct
16 Correct 1051 ms 468308 KB Output is correct
17 Correct 40 ms 31760 KB Output is correct
18 Correct 906 ms 318608 KB Output is correct
19 Correct 908 ms 310504 KB Output is correct
20 Correct 1241 ms 455404 KB Output is correct
21 Correct 1052 ms 261672 KB Output is correct
22 Correct 1665 ms 398944 KB Output is correct
23 Execution timed out 3587 ms 271284 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 25832 KB Output is correct
2 Correct 40 ms 26052 KB Output is correct
3 Correct 40 ms 26436 KB Output is correct
4 Correct 42 ms 26568 KB Output is correct
5 Correct 42 ms 27400 KB Output is correct
6 Correct 39 ms 26184 KB Output is correct
7 Correct 30 ms 25292 KB Output is correct
8 Correct 388 ms 88480 KB Output is correct
9 Correct 402 ms 88480 KB Output is correct
10 Correct 33 ms 25936 KB Output is correct
11 Correct 434 ms 89672 KB Output is correct
12 Correct 431 ms 89680 KB Output is correct
13 Correct 372 ms 95128 KB Output is correct
14 Correct 31 ms 25444 KB Output is correct
15 Correct 383 ms 83184 KB Output is correct
16 Correct 409 ms 78132 KB Output is correct
17 Correct 411 ms 78220 KB Output is correct
18 Correct 440 ms 78856 KB Output is correct
19 Correct 659 ms 88928 KB Output is correct
20 Correct 645 ms 87480 KB Output is correct
21 Correct 405 ms 85644 KB Output is correct
22 Correct 425 ms 86040 KB Output is correct
23 Correct 395 ms 79696 KB Output is correct
24 Correct 396 ms 79844 KB Output is correct
25 Correct 447 ms 86744 KB Output is correct
26 Correct 509 ms 82516 KB Output is correct
27 Correct 520 ms 83212 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25832 KB Output is correct
2 Correct 40 ms 26052 KB Output is correct
3 Correct 40 ms 26436 KB Output is correct
4 Correct 42 ms 26568 KB Output is correct
5 Correct 42 ms 27400 KB Output is correct
6 Correct 39 ms 26184 KB Output is correct
7 Correct 30 ms 25292 KB Output is correct
8 Correct 388 ms 88480 KB Output is correct
9 Correct 402 ms 88480 KB Output is correct
10 Correct 33 ms 25936 KB Output is correct
11 Correct 434 ms 89672 KB Output is correct
12 Correct 431 ms 89680 KB Output is correct
13 Correct 372 ms 95128 KB Output is correct
14 Correct 31 ms 25444 KB Output is correct
15 Correct 383 ms 83184 KB Output is correct
16 Correct 409 ms 78132 KB Output is correct
17 Correct 411 ms 78220 KB Output is correct
18 Correct 440 ms 78856 KB Output is correct
19 Correct 659 ms 88928 KB Output is correct
20 Correct 645 ms 87480 KB Output is correct
21 Correct 405 ms 85644 KB Output is correct
22 Correct 425 ms 86040 KB Output is correct
23 Correct 395 ms 79696 KB Output is correct
24 Correct 396 ms 79844 KB Output is correct
25 Correct 447 ms 86744 KB Output is correct
26 Correct 509 ms 82516 KB Output is correct
27 Correct 520 ms 83212 KB Output is correct
28 Correct 39 ms 32016 KB Output is correct
29 Correct 322 ms 225636 KB Output is correct
30 Correct 203 ms 208656 KB Output is correct
31 Correct 304 ms 245228 KB Output is correct
32 Correct 180 ms 141708 KB Output is correct
33 Correct 173 ms 156820 KB Output is correct
34 Correct 38 ms 32444 KB Output is correct
35 Correct 1204 ms 150492 KB Output is correct
36 Runtime error 1236 ms 524288 KB Execution killed with signal 9
37 Halted 0 ms 0 KB -