oj.uz

Submission #910129

# Submission time Handle Problem Language Result Execution time Memory
910129 2024-01-17T23:42:51 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 93368 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 = 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: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 37 ms 68436 KB Output is correct
2 Correct 43 ms 68800 KB Output is correct
3 Correct 49 ms 68948 KB Output is correct
4 Correct 50 ms 68948 KB Output is correct
5 Correct 41 ms 68952 KB Output is correct
6 Correct 52 ms 68944 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 68436 KB Output is correct
2 Correct 43 ms 68800 KB Output is correct
3 Correct 49 ms 68948 KB Output is correct
4 Correct 50 ms 68948 KB Output is correct
5 Correct 41 ms 68952 KB Output is correct
6 Correct 52 ms 68944 KB Output is correct
7 Correct 53 ms 68316 KB Output is correct
8 Correct 290 ms 68688 KB Output is correct
9 Correct 619 ms 68988 KB Output is correct
10 Correct 321 ms 68944 KB Output is correct
11 Correct 173 ms 69012 KB Output is correct
12 Correct 613 ms 69012 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68432 KB Output is correct
2 Correct 526 ms 85284 KB Output is correct
3 Correct 493 ms 85508 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68432 KB Output is correct
2 Correct 526 ms 85284 KB Output is correct
3 Correct 493 ms 85508 KB Output is correct
4 Correct 58 ms 68428 KB Output is correct
5 Correct 2813 ms 85504 KB Output is correct
6 Correct 1961 ms 85948 KB Output is correct
7 Correct 2528 ms 85816 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 68432 KB Output is correct
2 Correct 352 ms 89172 KB Output is correct
3 Correct 364 ms 89132 KB Output is correct
4 Correct 366 ms 89164 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 68432 KB Output is correct
2 Correct 352 ms 89172 KB Output is correct
3 Correct 364 ms 89132 KB Output is correct
4 Correct 366 ms 89164 KB Output is correct
5 Correct 37 ms 68436 KB Output is correct
6 Correct 546 ms 89076 KB Output is correct
7 Correct 1493 ms 93132 KB Output is correct
8 Correct 712 ms 88916 KB Output is correct
9 Correct 737 ms 89232 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 68444 KB Output is correct
2 Correct 331 ms 85380 KB Output is correct
3 Correct 373 ms 85360 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 68444 KB Output is correct
2 Correct 331 ms 85380 KB Output is correct
3 Correct 373 ms 85360 KB Output is correct
4 Correct 52 ms 68436 KB Output is correct
5 Correct 1662 ms 85380 KB Output is correct
6 Correct 554 ms 85504 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 68436 KB Output is correct
2 Correct 356 ms 89340 KB Output is correct
3 Correct 361 ms 89148 KB Output is correct
4 Correct 375 ms 89332 KB Output is correct
5 Correct 35 ms 68432 KB Output is correct
6 Correct 338 ms 85184 KB Output is correct
7 Correct 389 ms 85680 KB Output is correct
8 Correct 379 ms 85608 KB Output is correct
9 Correct 449 ms 85808 KB Output is correct
10 Correct 712 ms 87472 KB Output is correct
11 Correct 706 ms 87232 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 68436 KB Output is correct
2 Correct 356 ms 89340 KB Output is correct
3 Correct 361 ms 89148 KB Output is correct
4 Correct 375 ms 89332 KB Output is correct
5 Correct 35 ms 68432 KB Output is correct
6 Correct 338 ms 85184 KB Output is correct
7 Correct 389 ms 85680 KB Output is correct
8 Correct 379 ms 85608 KB Output is correct
9 Correct 449 ms 85808 KB Output is correct
10 Correct 712 ms 87472 KB Output is correct
11 Correct 706 ms 87232 KB Output is correct
12 Correct 42 ms 68436 KB Output is correct
13 Correct 591 ms 89248 KB Output is correct
14 Correct 1447 ms 93368 KB Output is correct
15 Correct 720 ms 88756 KB Output is correct
16 Correct 712 ms 89128 KB Output is correct
17 Correct 48 ms 68432 KB Output is correct
18 Correct 1659 ms 85308 KB Output is correct
19 Correct 569 ms 85284 KB Output is correct
20 Correct 763 ms 86016 KB Output is correct
21 Correct 642 ms 85840 KB Output is correct
22 Correct 3402 ms 88584 KB Output is correct
23 Execution timed out 3536 ms 91996 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 68308 KB Output is correct
2 Correct 41 ms 69004 KB Output is correct
3 Correct 48 ms 68944 KB Output is correct
4 Correct 48 ms 68948 KB Output is correct
5 Correct 41 ms 68956 KB Output is correct
6 Correct 51 ms 68948 KB Output is correct
7 Correct 41 ms 68468 KB Output is correct
8 Correct 492 ms 85312 KB Output is correct
9 Correct 478 ms 85540 KB Output is correct
10 Correct 34 ms 68432 KB Output is correct
11 Correct 362 ms 89200 KB Output is correct
12 Correct 356 ms 89160 KB Output is correct
13 Correct 355 ms 88916 KB Output is correct
14 Correct 35 ms 68436 KB Output is correct
15 Correct 318 ms 85260 KB Output is correct
16 Correct 379 ms 85476 KB Output is correct
17 Correct 367 ms 85812 KB Output is correct
18 Correct 448 ms 85864 KB Output is correct
19 Correct 669 ms 87892 KB Output is correct
20 Correct 666 ms 87076 KB Output is correct
21 Correct 466 ms 85180 KB Output is correct
22 Correct 467 ms 85792 KB Output is correct
23 Correct 458 ms 86088 KB Output is correct
24 Correct 443 ms 86184 KB Output is correct
25 Correct 471 ms 86536 KB Output is correct
26 Correct 495 ms 84820 KB Output is correct
27 Correct 527 ms 84824 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 68308 KB Output is correct
2 Correct 41 ms 69004 KB Output is correct
3 Correct 48 ms 68944 KB Output is correct
4 Correct 48 ms 68948 KB Output is correct
5 Correct 41 ms 68956 KB Output is correct
6 Correct 51 ms 68948 KB Output is correct
7 Correct 41 ms 68468 KB Output is correct
8 Correct 492 ms 85312 KB Output is correct
9 Correct 478 ms 85540 KB Output is correct
10 Correct 34 ms 68432 KB Output is correct
11 Correct 362 ms 89200 KB Output is correct
12 Correct 356 ms 89160 KB Output is correct
13 Correct 355 ms 88916 KB Output is correct
14 Correct 35 ms 68436 KB Output is correct
15 Correct 318 ms 85260 KB Output is correct
16 Correct 379 ms 85476 KB Output is correct
17 Correct 367 ms 85812 KB Output is correct
18 Correct 448 ms 85864 KB Output is correct
19 Correct 669 ms 87892 KB Output is correct
20 Correct 666 ms 87076 KB Output is correct
21 Correct 466 ms 85180 KB Output is correct
22 Correct 467 ms 85792 KB Output is correct
23 Correct 458 ms 86088 KB Output is correct
24 Correct 443 ms 86184 KB Output is correct
25 Correct 471 ms 86536 KB Output is correct
26 Correct 495 ms 84820 KB Output is correct
27 Correct 527 ms 84824 KB Output is correct
28 Correct 54 ms 68432 KB Output is correct
29 Correct 275 ms 68960 KB Output is correct
30 Correct 655 ms 69016 KB Output is correct
31 Correct 323 ms 68988 KB Output is correct
32 Correct 174 ms 68980 KB Output is correct
33 Correct 608 ms 69168 KB Output is correct
34 Correct 55 ms 68432 KB Output is correct
35 Correct 2792 ms 85856 KB Output is correct
36 Correct 1994 ms 86200 KB Output is correct
37 Correct 2535 ms 85824 KB Output is correct
38 Correct 39 ms 68436 KB Output is correct
39 Correct 546 ms 89188 KB Output is correct
40 Correct 1426 ms 93364 KB Output is correct
41 Correct 726 ms 88968 KB Output is correct
42 Correct 676 ms 88780 KB Output is correct
43 Correct 48 ms 68416 KB Output is correct
44 Correct 1620 ms 85172 KB Output is correct
45 Correct 579 ms 85500 KB Output is correct
46 Correct 718 ms 85868 KB Output is correct
47 Correct 654 ms 85832 KB Output is correct
48 Correct 3406 ms 88780 KB Output is correct
49 Execution timed out 3594 ms 92100 KB Time limit exceeded
50 Halted 0 ms 0 KB -