oj.uz

Submission #910128

# Submission time Handle Problem Language Result Execution time Memory
910128 2024-01-17T23:40:32 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 96152 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<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 = 350;
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:86:7: warning: unused variable 'S' [-Wunused-variable]
   86 |  auto S = chrono::steady_clock::now().time_since_epoch().count();
      |       ^
servers.cpp:119:5: warning: unused variable 's' [-Wunused-variable]
  119 |  ll s = 0;
      |     ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68272 KB Output is correct
2 Correct 46 ms 68972 KB Output is correct
3 Correct 49 ms 68944 KB Output is correct
4 Correct 44 ms 68872 KB Output is correct
5 Correct 49 ms 68948 KB Output is correct
6 Correct 53 ms 68856 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68272 KB Output is correct
2 Correct 46 ms 68972 KB Output is correct
3 Correct 49 ms 68944 KB Output is correct
4 Correct 44 ms 68872 KB Output is correct
5 Correct 49 ms 68948 KB Output is correct
6 Correct 53 ms 68856 KB Output is correct
7 Correct 64 ms 68256 KB Output is correct
8 Correct 318 ms 68888 KB Output is correct
9 Correct 671 ms 69304 KB Output is correct
10 Correct 363 ms 68976 KB Output is correct
11 Correct 216 ms 69056 KB Output is correct
12 Correct 623 ms 69352 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68432 KB Output is correct
2 Correct 536 ms 85768 KB Output is correct
3 Correct 500 ms 85256 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68432 KB Output is correct
2 Correct 536 ms 85768 KB Output is correct
3 Correct 500 ms 85256 KB Output is correct
4 Correct 61 ms 68436 KB Output is correct
5 Correct 2790 ms 85212 KB Output is correct
6 Correct 1903 ms 87632 KB Output is correct
7 Correct 2779 ms 87384 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 68444 KB Output is correct
2 Correct 362 ms 89204 KB Output is correct
3 Correct 379 ms 89160 KB Output is correct
4 Correct 347 ms 88912 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 68444 KB Output is correct
2 Correct 362 ms 89204 KB Output is correct
3 Correct 379 ms 89160 KB Output is correct
4 Correct 347 ms 88912 KB Output is correct
5 Correct 41 ms 68432 KB Output is correct
6 Correct 576 ms 88916 KB Output is correct
7 Correct 1560 ms 96152 KB Output is correct
8 Correct 785 ms 91740 KB Output is correct
9 Correct 813 ms 91520 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 68436 KB Output is correct
2 Correct 316 ms 85512 KB Output is correct
3 Correct 386 ms 85408 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 68436 KB Output is correct
2 Correct 316 ms 85512 KB Output is correct
3 Correct 386 ms 85408 KB Output is correct
4 Correct 52 ms 68484 KB Output is correct
5 Correct 1740 ms 85404 KB Output is correct
6 Correct 609 ms 88272 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 68436 KB Output is correct
2 Correct 348 ms 89144 KB Output is correct
3 Correct 364 ms 89424 KB Output is correct
4 Correct 339 ms 89100 KB Output is correct
5 Correct 36 ms 68436 KB Output is correct
6 Correct 333 ms 85272 KB Output is correct
7 Correct 359 ms 85436 KB Output is correct
8 Correct 403 ms 85780 KB Output is correct
9 Correct 462 ms 86112 KB Output is correct
10 Correct 699 ms 87488 KB Output is correct
11 Correct 673 ms 86896 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 68436 KB Output is correct
2 Correct 348 ms 89144 KB Output is correct
3 Correct 364 ms 89424 KB Output is correct
4 Correct 339 ms 89100 KB Output is correct
5 Correct 36 ms 68436 KB Output is correct
6 Correct 333 ms 85272 KB Output is correct
7 Correct 359 ms 85436 KB Output is correct
8 Correct 403 ms 85780 KB Output is correct
9 Correct 462 ms 86112 KB Output is correct
10 Correct 699 ms 87488 KB Output is correct
11 Correct 673 ms 86896 KB Output is correct
12 Correct 41 ms 68432 KB Output is correct
13 Correct 588 ms 88912 KB Output is correct
14 Correct 1477 ms 96144 KB Output is correct
15 Correct 797 ms 91936 KB Output is correct
16 Correct 798 ms 91696 KB Output is correct
17 Correct 51 ms 69192 KB Output is correct
18 Correct 1711 ms 88248 KB Output is correct
19 Correct 624 ms 88524 KB Output is correct
20 Correct 847 ms 88728 KB Output is correct
21 Correct 752 ms 88756 KB Output is correct
22 Execution timed out 3536 ms 91444 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68428 KB Output is correct
2 Correct 44 ms 68944 KB Output is correct
3 Correct 51 ms 69012 KB Output is correct
4 Correct 45 ms 68944 KB Output is correct
5 Correct 41 ms 68944 KB Output is correct
6 Correct 51 ms 68956 KB Output is correct
7 Correct 40 ms 68432 KB Output is correct
8 Correct 504 ms 85592 KB Output is correct
9 Correct 544 ms 85412 KB Output is correct
10 Correct 35 ms 68432 KB Output is correct
11 Correct 397 ms 89168 KB Output is correct
12 Correct 371 ms 89024 KB Output is correct
13 Correct 380 ms 89168 KB Output is correct
14 Correct 35 ms 68436 KB Output is correct
15 Correct 336 ms 85184 KB Output is correct
16 Correct 381 ms 85328 KB Output is correct
17 Correct 384 ms 85788 KB Output is correct
18 Correct 443 ms 86136 KB Output is correct
19 Correct 693 ms 87892 KB Output is correct
20 Correct 700 ms 87016 KB Output is correct
21 Correct 521 ms 85332 KB Output is correct
22 Correct 525 ms 85364 KB Output is correct
23 Correct 466 ms 86080 KB Output is correct
24 Correct 467 ms 86096 KB Output is correct
25 Correct 481 ms 85960 KB Output is correct
26 Correct 537 ms 84952 KB Output is correct
27 Correct 494 ms 84992 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68428 KB Output is correct
2 Correct 44 ms 68944 KB Output is correct
3 Correct 51 ms 69012 KB Output is correct
4 Correct 45 ms 68944 KB Output is correct
5 Correct 41 ms 68944 KB Output is correct
6 Correct 51 ms 68956 KB Output is correct
7 Correct 40 ms 68432 KB Output is correct
8 Correct 504 ms 85592 KB Output is correct
9 Correct 544 ms 85412 KB Output is correct
10 Correct 35 ms 68432 KB Output is correct
11 Correct 397 ms 89168 KB Output is correct
12 Correct 371 ms 89024 KB Output is correct
13 Correct 380 ms 89168 KB Output is correct
14 Correct 35 ms 68436 KB Output is correct
15 Correct 336 ms 85184 KB Output is correct
16 Correct 381 ms 85328 KB Output is correct
17 Correct 384 ms 85788 KB Output is correct
18 Correct 443 ms 86136 KB Output is correct
19 Correct 693 ms 87892 KB Output is correct
20 Correct 700 ms 87016 KB Output is correct
21 Correct 521 ms 85332 KB Output is correct
22 Correct 525 ms 85364 KB Output is correct
23 Correct 466 ms 86080 KB Output is correct
24 Correct 467 ms 86096 KB Output is correct
25 Correct 481 ms 85960 KB Output is correct
26 Correct 537 ms 84952 KB Output is correct
27 Correct 494 ms 84992 KB Output is correct
28 Correct 60 ms 68404 KB Output is correct
29 Correct 315 ms 68808 KB Output is correct
30 Correct 688 ms 69140 KB Output is correct
31 Correct 368 ms 70108 KB Output is correct
32 Correct 217 ms 70088 KB Output is correct
33 Correct 643 ms 70356 KB Output is correct
34 Correct 57 ms 69200 KB Output is correct
35 Correct 3133 ms 88460 KB Output is correct
36 Correct 1931 ms 87412 KB Output is correct
37 Correct 2701 ms 87752 KB Output is correct
38 Correct 41 ms 69212 KB Output is correct
39 Correct 594 ms 91960 KB Output is correct
40 Correct 1530 ms 96140 KB Output is correct
41 Correct 802 ms 91848 KB Output is correct
42 Correct 776 ms 91804 KB Output is correct
43 Correct 51 ms 69204 KB Output is correct
44 Correct 1684 ms 88524 KB Output is correct
45 Correct 611 ms 88764 KB Output is correct
46 Correct 911 ms 88824 KB Output is correct
47 Correct 724 ms 89004 KB Output is correct
48 Execution timed out 3526 ms 91208 KB Time limit exceeded
49 Halted 0 ms 0 KB -