oj.uz

Submission #910133

# Submission time Handle Problem Language Result Execution time Memory
910133 2024-01-17T23:48:35 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 90496 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define SZ(x) (int) x.size()

const int N = 120'005;
vector<array<int, 3>> adj[N];
//0: increasing, 1: decreasing, {ancestor, last weight}
array<int, 3> bl[2][18][N];
int st[N], en[N], curt;
void dfs(int i, int par, int part) {
	bl[0][0][i] = {par, part, part};
	bl[1][0][i] = {par, part, part};
	for (int j = 1; j < 18; j++) {
		bl[0][j][i] = bl[0][j - 1][i];
		auto [lst, lstt, mx] = bl[0][j][i];
		if (lstt <= bl[0][0][lst][1]) {
			bl[0][j][i] = bl[0][j - 1][lst];
			bl[0][j][i][2] = max(bl[0][j][i][2], mx);
		}
	}
	for (int j = 1; j < 18; j++) {
		bl[1][j][i] = bl[1][j - 1][i];
		auto [lst, lstt, mx] = bl[1][j][i];
		if (lstt >= bl[1][0][lst][1]) {
			bl[1][j][i] = bl[1][j - 1][lst];
			bl[1][j][i][2] = max(bl[1][j][i][2], mx);
		}
	}
	st[i] = curt++;
	for (auto [nxt, t, nxtidx] : adj[i]) {
		if (nxt == par) continue;
		dfs(nxt, i, t);
	}
	en[i] = curt;
}
bool lca(int l, int b) {
	if (st[l] <= st[b] && en[b] <= en[l]) {
		return 1;
	}
	return 0;
}
array<int, 2> check(int t, int a, int b) {
	int mx = -1e9, high = bl[t][17][a][0];
	if (!lca(high, b)) {
		return {int(1e9), 0};
	}
	if (a == high || lca(a, b)) {
		return {int(-1e9), (t == 1? 1 : -1) * int(1e9)};
	}
	for (int j = 17; j >= 0; j--) {
		if (!lca(bl[t][j][a][0], b) && !lca(bl[t][j][a][0], high)) {
			mx = max(mx, bl[t][j][a][2]);
			a = bl[t][j][a][0];
		}
	}
	return {max(mx, bl[t][0][a][2]), bl[t][0][a][1]};
}
vector<int> dp[N];
int lst;
int solve(int i, int par) {
	if (~dp[i][par]) return dp[i][par];
	int prv = -1;
	if (par < SZ(adj[i])) prv = adj[i][par][1];
	dp[i][par] = 1;
	for (int j = 0; j < SZ(adj[i]); j++) {
		auto [nxt, t, nxtidx] = adj[i][j];
		if (t > lst) break;
		if (j == par || prv >= t) continue;
		dp[i][par] += solve(nxt, nxtidx);
	}
	return dp[i][par];
}
bool checkpath(int a, int b, int t, bool x) {
	array<int, 2> l = check(x, a, b), r = check(!x, b, a);
	if (l[0] <= t && r[0] <= t && (l[1] == r[1] || (x ^ (l[1] < r[1]))) ) {
		return 1;
	} else {
		return 0;
	}
}
const int B = 300;
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	auto S = chrono::steady_clock::now().time_since_epoch().count();
	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, 1, 0);
	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;
	ll s = 0;
	for (int i = 0; i < q; i++) {
		if (upd.size() == B) {
// 			for (auto [a, b, t] : upd) {
// 				int x = curadj[b].size(), y = curadj[a].size();
// 				curadj[a].push_back({b, t, x});
// 				curadj[b].push_back({a, t, y});
// 			}
			lst = i - 1;
			upd.clear();
			for (int i = 1; i <= n; i++) {
				for (int j = 0; j <= SZ(adj[i]); j++) {
					dp[i][j] = -1;
				}
			}
		}
		if (v[i].first == 'S') {
			int a = v[i].second[0], b = 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];
#ifdef MINA
// 			cout << i << endl;
			s += (checkpath(a, b, i, 1));
#else
			cout << (checkpath(a, b, i, 1)? "yes\n" : "no\n");
#endif
		} else {
			int x = v[i].second[0];
			int ans = solve(x, adj[x].size());
			for (auto [a, b, t] : upd) {
				ans += checkpath(x, b, t - 1, 0) || checkpath(x, a, t - 1, 0);
			}
#ifdef MINA
// 			cout << i << endl;
			s += ans;
#else
			cout << ans << '\n';
#endif
		}
	}
#ifdef MINA
	cout << s << '\n';
	auto E = chrono::steady_clock::now().time_since_epoch().count();
	cout << (E - S) / 1e9 << 's';
#endif
	return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:85:7: warning: unused variable 'S' [-Wunused-variable]
   85 |  auto S = chrono::steady_clock::now().time_since_epoch().count();
      |       ^
servers.cpp:118:5: warning: unused variable 's' [-Wunused-variable]
  118 |  ll s = 0;
      |     ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65620 KB Output is correct
2 Correct 42 ms 66132 KB Output is correct
3 Correct 55 ms 66128 KB Output is correct
4 Correct 44 ms 66128 KB Output is correct
5 Correct 43 ms 66132 KB Output is correct
6 Correct 51 ms 66128 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65620 KB Output is correct
2 Correct 42 ms 66132 KB Output is correct
3 Correct 55 ms 66128 KB Output is correct
4 Correct 44 ms 66128 KB Output is correct
5 Correct 43 ms 66132 KB Output is correct
6 Correct 51 ms 66128 KB Output is correct
7 Correct 56 ms 65616 KB Output is correct
8 Correct 298 ms 66260 KB Output is correct
9 Correct 597 ms 66128 KB Output is correct
10 Correct 326 ms 66192 KB Output is correct
11 Correct 157 ms 66132 KB Output is correct
12 Correct 488 ms 66132 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 65464 KB Output is correct
2 Correct 524 ms 82628 KB Output is correct
3 Correct 516 ms 82436 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 65464 KB Output is correct
2 Correct 524 ms 82628 KB Output is correct
3 Correct 516 ms 82436 KB Output is correct
4 Correct 57 ms 65616 KB Output is correct
5 Correct 3065 ms 82692 KB Output is correct
6 Correct 1959 ms 82948 KB Output is correct
7 Correct 2736 ms 82696 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65616 KB Output is correct
2 Correct 394 ms 86588 KB Output is correct
3 Correct 373 ms 86384 KB Output is correct
4 Correct 391 ms 86364 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65616 KB Output is correct
2 Correct 394 ms 86588 KB Output is correct
3 Correct 373 ms 86384 KB Output is correct
4 Correct 391 ms 86364 KB Output is correct
5 Correct 40 ms 65400 KB Output is correct
6 Correct 596 ms 86236 KB Output is correct
7 Correct 1550 ms 90496 KB Output is correct
8 Correct 728 ms 86100 KB Output is correct
9 Correct 750 ms 86196 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65488 KB Output is correct
2 Correct 340 ms 82364 KB Output is correct
3 Correct 383 ms 82440 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65488 KB Output is correct
2 Correct 340 ms 82364 KB Output is correct
3 Correct 383 ms 82440 KB Output is correct
4 Correct 50 ms 65448 KB Output is correct
5 Correct 1692 ms 83284 KB Output is correct
6 Correct 619 ms 82512 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 65436 KB Output is correct
2 Correct 374 ms 86372 KB Output is correct
3 Correct 384 ms 86360 KB Output is correct
4 Correct 391 ms 86100 KB Output is correct
5 Correct 37 ms 65508 KB Output is correct
6 Correct 347 ms 82516 KB Output is correct
7 Correct 409 ms 83260 KB Output is correct
8 Correct 394 ms 83032 KB Output is correct
9 Correct 463 ms 83152 KB Output is correct
10 Correct 759 ms 84924 KB Output is correct
11 Correct 753 ms 84376 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 65436 KB Output is correct
2 Correct 374 ms 86372 KB Output is correct
3 Correct 384 ms 86360 KB Output is correct
4 Correct 391 ms 86100 KB Output is correct
5 Correct 37 ms 65508 KB Output is correct
6 Correct 347 ms 82516 KB Output is correct
7 Correct 409 ms 83260 KB Output is correct
8 Correct 394 ms 83032 KB Output is correct
9 Correct 463 ms 83152 KB Output is correct
10 Correct 759 ms 84924 KB Output is correct
11 Correct 753 ms 84376 KB Output is correct
12 Correct 41 ms 65620 KB Output is correct
13 Correct 594 ms 86604 KB Output is correct
14 Correct 1584 ms 90192 KB Output is correct
15 Correct 743 ms 86076 KB Output is correct
16 Correct 765 ms 86156 KB Output is correct
17 Correct 51 ms 65364 KB Output is correct
18 Correct 1667 ms 82616 KB Output is correct
19 Correct 622 ms 82688 KB Output is correct
20 Correct 842 ms 83028 KB Output is correct
21 Correct 702 ms 83240 KB Output is correct
22 Correct 3216 ms 85912 KB Output is correct
23 Execution timed out 3573 ms 86376 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 65616 KB Output is correct
2 Correct 45 ms 66144 KB Output is correct
3 Correct 49 ms 66132 KB Output is correct
4 Correct 49 ms 66132 KB Output is correct
5 Correct 43 ms 66148 KB Output is correct
6 Correct 51 ms 66132 KB Output is correct
7 Correct 39 ms 65628 KB Output is correct
8 Correct 524 ms 82552 KB Output is correct
9 Correct 512 ms 82692 KB Output is correct
10 Correct 34 ms 65628 KB Output is correct
11 Correct 372 ms 86352 KB Output is correct
12 Correct 382 ms 86476 KB Output is correct
13 Correct 370 ms 86168 KB Output is correct
14 Correct 38 ms 65620 KB Output is correct
15 Correct 357 ms 82564 KB Output is correct
16 Correct 419 ms 82512 KB Output is correct
17 Correct 392 ms 83024 KB Output is correct
18 Correct 463 ms 83464 KB Output is correct
19 Correct 754 ms 84760 KB Output is correct
20 Correct 725 ms 84352 KB Output is correct
21 Correct 485 ms 82544 KB Output is correct
22 Correct 501 ms 82564 KB Output is correct
23 Correct 479 ms 83220 KB Output is correct
24 Correct 456 ms 83216 KB Output is correct
25 Correct 471 ms 83208 KB Output is correct
26 Correct 543 ms 82000 KB Output is correct
27 Correct 503 ms 82004 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 65616 KB Output is correct
2 Correct 45 ms 66144 KB Output is correct
3 Correct 49 ms 66132 KB Output is correct
4 Correct 49 ms 66132 KB Output is correct
5 Correct 43 ms 66148 KB Output is correct
6 Correct 51 ms 66132 KB Output is correct
7 Correct 39 ms 65628 KB Output is correct
8 Correct 524 ms 82552 KB Output is correct
9 Correct 512 ms 82692 KB Output is correct
10 Correct 34 ms 65628 KB Output is correct
11 Correct 372 ms 86352 KB Output is correct
12 Correct 382 ms 86476 KB Output is correct
13 Correct 370 ms 86168 KB Output is correct
14 Correct 38 ms 65620 KB Output is correct
15 Correct 357 ms 82564 KB Output is correct
16 Correct 419 ms 82512 KB Output is correct
17 Correct 392 ms 83024 KB Output is correct
18 Correct 463 ms 83464 KB Output is correct
19 Correct 754 ms 84760 KB Output is correct
20 Correct 725 ms 84352 KB Output is correct
21 Correct 485 ms 82544 KB Output is correct
22 Correct 501 ms 82564 KB Output is correct
23 Correct 479 ms 83220 KB Output is correct
24 Correct 456 ms 83216 KB Output is correct
25 Correct 471 ms 83208 KB Output is correct
26 Correct 543 ms 82000 KB Output is correct
27 Correct 503 ms 82004 KB Output is correct
28 Correct 58 ms 65604 KB Output is correct
29 Correct 274 ms 65884 KB Output is correct
30 Correct 601 ms 66384 KB Output is correct
31 Correct 323 ms 65960 KB Output is correct
32 Correct 168 ms 66260 KB Output is correct
33 Correct 481 ms 66132 KB Output is correct
34 Correct 58 ms 65616 KB Output is correct
35 Correct 3134 ms 83024 KB Output is correct
36 Correct 1947 ms 83016 KB Output is correct
37 Correct 2536 ms 82724 KB Output is correct
38 Correct 41 ms 65616 KB Output is correct
39 Correct 576 ms 86064 KB Output is correct
40 Correct 1509 ms 90204 KB Output is correct
41 Correct 772 ms 86100 KB Output is correct
42 Correct 729 ms 86100 KB Output is correct
43 Correct 54 ms 65616 KB Output is correct
44 Correct 1657 ms 82696 KB Output is correct
45 Correct 606 ms 82772 KB Output is correct
46 Correct 829 ms 83196 KB Output is correct
47 Correct 693 ms 83028 KB Output is correct
48 Correct 3268 ms 85756 KB Output is correct
49 Execution timed out 3596 ms 86444 KB Time limit exceeded
50 Halted 0 ms 0 KB -