oj.uz

Submission #912794

# Submission time Handle Problem Language Result Execution time Memory
912794 2024-01-19T23:16:25 Z MinaRagy06 Inside information (BOI21_servers) C++17
50 / 100
 691 ms 96020 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, 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;
	}
// 	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;
	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});
			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({x, b, t - 1, i});
// 				} else {
// 					int mid = lca.query(a, x);
// 					ask[mid].push_back({x, a, t - 1, i});
// 				}
// 			}

			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});
				}
			}

// 			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;
// 			}
		}
	}
	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 26448 KB Output is correct
2 Correct 37 ms 28872 KB Output is correct
3 Correct 46 ms 29144 KB Output is correct
4 Correct 42 ms 29128 KB Output is correct
5 Correct 39 ms 29780 KB Output is correct
6 Correct 46 ms 29128 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26448 KB Output is correct
2 Correct 37 ms 28872 KB Output is correct
3 Correct 46 ms 29144 KB Output is correct
4 Correct 42 ms 29128 KB Output is correct
5 Correct 39 ms 29780 KB Output is correct
6 Correct 46 ms 29128 KB Output is correct
7 Incorrect 35 ms 29252 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26316 KB Output is correct
2 Correct 402 ms 87544 KB Output is correct
3 Correct 406 ms 87300 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26316 KB Output is correct
2 Correct 402 ms 87544 KB Output is correct
3 Correct 406 ms 87300 KB Output is correct
4 Incorrect 35 ms 30924 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 26448 KB Output is correct
2 Correct 458 ms 90672 KB Output is correct
3 Correct 466 ms 90948 KB Output is correct
4 Correct 390 ms 96020 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 26448 KB Output is correct
2 Correct 458 ms 90672 KB Output is correct
3 Correct 466 ms 90948 KB Output is correct
4 Correct 390 ms 96020 KB Output is correct
5 Incorrect 34 ms 29132 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26132 KB Output is correct
2 Correct 397 ms 82364 KB Output is correct
3 Correct 437 ms 77312 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26132 KB Output is correct
2 Correct 397 ms 82364 KB Output is correct
3 Correct 437 ms 77312 KB Output is correct
4 Incorrect 34 ms 28864 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26460 KB Output is correct
2 Correct 485 ms 90748 KB Output is correct
3 Correct 461 ms 90708 KB Output is correct
4 Correct 444 ms 95824 KB Output is correct
5 Correct 29 ms 26196 KB Output is correct
6 Correct 376 ms 82596 KB Output is correct
7 Correct 422 ms 77396 KB Output is correct
8 Correct 435 ms 77180 KB Output is correct
9 Correct 485 ms 77948 KB Output is correct
10 Correct 691 ms 88944 KB Output is correct
11 Correct 643 ms 87224 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26460 KB Output is correct
2 Correct 485 ms 90748 KB Output is correct
3 Correct 461 ms 90708 KB Output is correct
4 Correct 444 ms 95824 KB Output is correct
5 Correct 29 ms 26196 KB Output is correct
6 Correct 376 ms 82596 KB Output is correct
7 Correct 422 ms 77396 KB Output is correct
8 Correct 435 ms 77180 KB Output is correct
9 Correct 485 ms 77948 KB Output is correct
10 Correct 691 ms 88944 KB Output is correct
11 Correct 643 ms 87224 KB Output is correct
12 Incorrect 33 ms 29144 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26436 KB Output is correct
2 Correct 39 ms 28876 KB Output is correct
3 Correct 39 ms 29084 KB Output is correct
4 Correct 40 ms 28980 KB Output is correct
5 Correct 41 ms 29756 KB Output is correct
6 Correct 37 ms 29128 KB Output is correct
7 Correct 28 ms 26056 KB Output is correct
8 Correct 386 ms 87452 KB Output is correct
9 Correct 395 ms 87316 KB Output is correct
10 Correct 29 ms 26460 KB Output is correct
11 Correct 478 ms 90976 KB Output is correct
12 Correct 476 ms 90832 KB Output is correct
13 Correct 370 ms 95828 KB Output is correct
14 Correct 29 ms 26200 KB Output is correct
15 Correct 415 ms 82760 KB Output is correct
16 Correct 408 ms 77380 KB Output is correct
17 Correct 449 ms 77492 KB Output is correct
18 Correct 491 ms 77904 KB Output is correct
19 Correct 683 ms 88656 KB Output is correct
20 Correct 681 ms 87244 KB Output is correct
21 Correct 435 ms 84760 KB Output is correct
22 Correct 405 ms 84540 KB Output is correct
23 Correct 400 ms 78416 KB Output is correct
24 Correct 411 ms 78928 KB Output is correct
25 Correct 442 ms 85768 KB Output is correct
26 Correct 553 ms 81320 KB Output is correct
27 Correct 550 ms 81792 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26436 KB Output is correct
2 Correct 39 ms 28876 KB Output is correct
3 Correct 39 ms 29084 KB Output is correct
4 Correct 40 ms 28980 KB Output is correct
5 Correct 41 ms 29756 KB Output is correct
6 Correct 37 ms 29128 KB Output is correct
7 Correct 28 ms 26056 KB Output is correct
8 Correct 386 ms 87452 KB Output is correct
9 Correct 395 ms 87316 KB Output is correct
10 Correct 29 ms 26460 KB Output is correct
11 Correct 478 ms 90976 KB Output is correct
12 Correct 476 ms 90832 KB Output is correct
13 Correct 370 ms 95828 KB Output is correct
14 Correct 29 ms 26200 KB Output is correct
15 Correct 415 ms 82760 KB Output is correct
16 Correct 408 ms 77380 KB Output is correct
17 Correct 449 ms 77492 KB Output is correct
18 Correct 491 ms 77904 KB Output is correct
19 Correct 683 ms 88656 KB Output is correct
20 Correct 681 ms 87244 KB Output is correct
21 Correct 435 ms 84760 KB Output is correct
22 Correct 405 ms 84540 KB Output is correct
23 Correct 400 ms 78416 KB Output is correct
24 Correct 411 ms 78928 KB Output is correct
25 Correct 442 ms 85768 KB Output is correct
26 Correct 553 ms 81320 KB Output is correct
27 Correct 550 ms 81792 KB Output is correct
28 Incorrect 35 ms 29244 KB Extra information in the output file
29 Halted 0 ms 0 KB -