oj.uz

Submission #910132

# Submission time Handle Problem Language Result Execution time Memory
910132 2024-01-17T23:46:50 Z MinaRagy06 Inside information (BOI21_servers) C++17
67.5 / 100
 3500 ms 93284 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;
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<array<int, 3>> curadj[N];
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 = 400;
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:87:7: warning: unused variable 'S' [-Wunused-variable]
   87 |  auto S = chrono::steady_clock::now().time_since_epoch().count();
      |       ^
servers.cpp:120:5: warning: unused variable 's' [-Wunused-variable]
  120 |  ll s = 0;
      |     ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 68224 KB Output is correct
2 Correct 45 ms 68956 KB Output is correct
3 Correct 64 ms 68948 KB Output is correct
4 Correct 52 ms 68932 KB Output is correct
5 Correct 42 ms 68948 KB Output is correct
6 Correct 46 ms 69012 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 68224 KB Output is correct
2 Correct 45 ms 68956 KB Output is correct
3 Correct 64 ms 68948 KB Output is correct
4 Correct 52 ms 68932 KB Output is correct
5 Correct 42 ms 68948 KB Output is correct
6 Correct 46 ms 69012 KB Output is correct
7 Correct 53 ms 68412 KB Output is correct
8 Correct 332 ms 68900 KB Output is correct
9 Correct 826 ms 68948 KB Output is correct
10 Correct 432 ms 69116 KB Output is correct
11 Correct 409 ms 69020 KB Output is correct
12 Correct 1334 ms 69292 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 68436 KB Output is correct
2 Correct 566 ms 85416 KB Output is correct
3 Correct 472 ms 85248 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 68436 KB Output is correct
2 Correct 566 ms 85416 KB Output is correct
3 Correct 472 ms 85248 KB Output is correct
4 Correct 55 ms 68452 KB Output is correct
5 Execution timed out 3553 ms 85440 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 68440 KB Output is correct
2 Correct 351 ms 89100 KB Output is correct
3 Correct 350 ms 89212 KB Output is correct
4 Correct 369 ms 89096 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 68440 KB Output is correct
2 Correct 351 ms 89100 KB Output is correct
3 Correct 350 ms 89212 KB Output is correct
4 Correct 369 ms 89096 KB Output is correct
5 Correct 50 ms 68432 KB Output is correct
6 Correct 546 ms 88920 KB Output is correct
7 Correct 1574 ms 93088 KB Output is correct
8 Correct 725 ms 88872 KB Output is correct
9 Correct 818 ms 89076 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68432 KB Output is correct
2 Correct 309 ms 85316 KB Output is correct
3 Correct 387 ms 85376 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68432 KB Output is correct
2 Correct 309 ms 85316 KB Output is correct
3 Correct 387 ms 85376 KB Output is correct
4 Correct 48 ms 68424 KB Output is correct
5 Correct 2051 ms 85632 KB Output is correct
6 Correct 565 ms 85340 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 68436 KB Output is correct
2 Correct 332 ms 89172 KB Output is correct
3 Correct 334 ms 89172 KB Output is correct
4 Correct 337 ms 89180 KB Output is correct
5 Correct 35 ms 68304 KB Output is correct
6 Correct 312 ms 85612 KB Output is correct
7 Correct 346 ms 85368 KB Output is correct
8 Correct 372 ms 85756 KB Output is correct
9 Correct 430 ms 86044 KB Output is correct
10 Correct 630 ms 87764 KB Output is correct
11 Correct 632 ms 87404 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 68436 KB Output is correct
2 Correct 332 ms 89172 KB Output is correct
3 Correct 334 ms 89172 KB Output is correct
4 Correct 337 ms 89180 KB Output is correct
5 Correct 35 ms 68304 KB Output is correct
6 Correct 312 ms 85612 KB Output is correct
7 Correct 346 ms 85368 KB Output is correct
8 Correct 372 ms 85756 KB Output is correct
9 Correct 430 ms 86044 KB Output is correct
10 Correct 630 ms 87764 KB Output is correct
11 Correct 632 ms 87404 KB Output is correct
12 Correct 38 ms 68444 KB Output is correct
13 Correct 542 ms 89212 KB Output is correct
14 Correct 1384 ms 92936 KB Output is correct
15 Correct 697 ms 89000 KB Output is correct
16 Correct 723 ms 89008 KB Output is correct
17 Correct 49 ms 68436 KB Output is correct
18 Correct 1875 ms 85700 KB Output is correct
19 Correct 558 ms 85332 KB Output is correct
20 Correct 811 ms 85888 KB Output is correct
21 Correct 667 ms 86308 KB Output is correct
22 Correct 3492 ms 89072 KB Output is correct
23 Execution timed out 3590 ms 89604 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68436 KB Output is correct
2 Correct 42 ms 68960 KB Output is correct
3 Correct 47 ms 69200 KB Output is correct
4 Correct 44 ms 68948 KB Output is correct
5 Correct 41 ms 68948 KB Output is correct
6 Correct 52 ms 69008 KB Output is correct
7 Correct 37 ms 68432 KB Output is correct
8 Correct 447 ms 85252 KB Output is correct
9 Correct 489 ms 85380 KB Output is correct
10 Correct 35 ms 68436 KB Output is correct
11 Correct 350 ms 89288 KB Output is correct
12 Correct 332 ms 89168 KB Output is correct
13 Correct 348 ms 89324 KB Output is correct
14 Correct 43 ms 68432 KB Output is correct
15 Correct 313 ms 85332 KB Output is correct
16 Correct 354 ms 85268 KB Output is correct
17 Correct 352 ms 85812 KB Output is correct
18 Correct 434 ms 85840 KB Output is correct
19 Correct 621 ms 87632 KB Output is correct
20 Correct 632 ms 86960 KB Output is correct
21 Correct 451 ms 85208 KB Output is correct
22 Correct 451 ms 85708 KB Output is correct
23 Correct 446 ms 86096 KB Output is correct
24 Correct 450 ms 86232 KB Output is correct
25 Correct 445 ms 85936 KB Output is correct
26 Correct 471 ms 84816 KB Output is correct
27 Correct 431 ms 84944 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68436 KB Output is correct
2 Correct 42 ms 68960 KB Output is correct
3 Correct 47 ms 69200 KB Output is correct
4 Correct 44 ms 68948 KB Output is correct
5 Correct 41 ms 68948 KB Output is correct
6 Correct 52 ms 69008 KB Output is correct
7 Correct 37 ms 68432 KB Output is correct
8 Correct 447 ms 85252 KB Output is correct
9 Correct 489 ms 85380 KB Output is correct
10 Correct 35 ms 68436 KB Output is correct
11 Correct 350 ms 89288 KB Output is correct
12 Correct 332 ms 89168 KB Output is correct
13 Correct 348 ms 89324 KB Output is correct
14 Correct 43 ms 68432 KB Output is correct
15 Correct 313 ms 85332 KB Output is correct
16 Correct 354 ms 85268 KB Output is correct
17 Correct 352 ms 85812 KB Output is correct
18 Correct 434 ms 85840 KB Output is correct
19 Correct 621 ms 87632 KB Output is correct
20 Correct 632 ms 86960 KB Output is correct
21 Correct 451 ms 85208 KB Output is correct
22 Correct 451 ms 85708 KB Output is correct
23 Correct 446 ms 86096 KB Output is correct
24 Correct 450 ms 86232 KB Output is correct
25 Correct 445 ms 85936 KB Output is correct
26 Correct 471 ms 84816 KB Output is correct
27 Correct 431 ms 84944 KB Output is correct
28 Correct 54 ms 68432 KB Output is correct
29 Correct 304 ms 68904 KB Output is correct
30 Correct 759 ms 68944 KB Output is correct
31 Correct 367 ms 68956 KB Output is correct
32 Correct 410 ms 68872 KB Output is correct
33 Correct 1235 ms 69460 KB Output is correct
34 Correct 55 ms 68432 KB Output is correct
35 Correct 2430 ms 85324 KB Output is correct
36 Correct 1838 ms 85912 KB Output is correct
37 Correct 2686 ms 85664 KB Output is correct
38 Correct 39 ms 68272 KB Output is correct
39 Correct 524 ms 88988 KB Output is correct
40 Correct 1396 ms 93284 KB Output is correct
41 Correct 704 ms 89168 KB Output is correct
42 Correct 728 ms 88932 KB Output is correct
43 Correct 52 ms 68432 KB Output is correct
44 Correct 1883 ms 85492 KB Output is correct
45 Correct 578 ms 85492 KB Output is correct
46 Correct 795 ms 85736 KB Output is correct
47 Correct 674 ms 86008 KB Output is correct
48 Execution timed out 3522 ms 88336 KB Time limit exceeded
49 Halted 0 ms 0 KB -