oj.uz

Submission #910136

# Submission time Handle Problem Language Result Execution time Memory
910136 2024-01-17T23:57:16 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 90648 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 isanc(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 (!isanc(high, b)) {
		return {int(1e9), 0};
	}
	if (a == high || isanc(a, b)) {
		return {int(-1e9), (t == 1? 1 : -1) * int(1e9)};
	}
	for (int j = 17; j >= 0; j--) {
		if (!isanc(bl[t][j][a][0], b) && !isanc(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];
			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];
#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) {
				if (isanc(b, x)) {
					ans += checkpath(x, b, t - 1, 0);
				} else {
					ans += 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 35 ms 65488 KB Output is correct
2 Correct 39 ms 66132 KB Output is correct
3 Correct 45 ms 66128 KB Output is correct
4 Correct 45 ms 66128 KB Output is correct
5 Correct 39 ms 66140 KB Output is correct
6 Correct 46 ms 66132 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 65488 KB Output is correct
2 Correct 39 ms 66132 KB Output is correct
3 Correct 45 ms 66128 KB Output is correct
4 Correct 45 ms 66128 KB Output is correct
5 Correct 39 ms 66140 KB Output is correct
6 Correct 46 ms 66132 KB Output is correct
7 Correct 49 ms 65616 KB Output is correct
8 Correct 170 ms 66100 KB Output is correct
9 Correct 334 ms 66228 KB Output is correct
10 Correct 169 ms 66144 KB Output is correct
11 Correct 92 ms 66132 KB Output is correct
12 Correct 233 ms 66108 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65576 KB Output is correct
2 Correct 559 ms 82696 KB Output is correct
3 Correct 547 ms 82948 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65576 KB Output is correct
2 Correct 559 ms 82696 KB Output is correct
3 Correct 547 ms 82948 KB Output is correct
4 Correct 45 ms 65424 KB Output is correct
5 Correct 2695 ms 82692 KB Output is correct
6 Correct 1381 ms 82948 KB Output is correct
7 Correct 1963 ms 82968 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 65628 KB Output is correct
2 Correct 395 ms 86352 KB Output is correct
3 Correct 413 ms 86356 KB Output is correct
4 Correct 426 ms 86148 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 65628 KB Output is correct
2 Correct 395 ms 86352 KB Output is correct
3 Correct 413 ms 86356 KB Output is correct
4 Correct 426 ms 86148 KB Output is correct
5 Correct 36 ms 65372 KB Output is correct
6 Correct 497 ms 86236 KB Output is correct
7 Correct 1474 ms 90068 KB Output is correct
8 Correct 602 ms 86056 KB Output is correct
9 Correct 581 ms 86004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65620 KB Output is correct
2 Correct 351 ms 82352 KB Output is correct
3 Correct 450 ms 82628 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65620 KB Output is correct
2 Correct 351 ms 82352 KB Output is correct
3 Correct 450 ms 82628 KB Output is correct
4 Correct 42 ms 65616 KB Output is correct
5 Correct 1056 ms 82540 KB Output is correct
6 Correct 522 ms 82432 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65616 KB Output is correct
2 Correct 430 ms 86444 KB Output is correct
3 Correct 415 ms 86296 KB Output is correct
4 Correct 400 ms 86096 KB Output is correct
5 Correct 33 ms 65624 KB Output is correct
6 Correct 378 ms 82768 KB Output is correct
7 Correct 400 ms 82572 KB Output is correct
8 Correct 426 ms 82992 KB Output is correct
9 Correct 496 ms 83024 KB Output is correct
10 Correct 744 ms 84676 KB Output is correct
11 Correct 740 ms 84048 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65616 KB Output is correct
2 Correct 430 ms 86444 KB Output is correct
3 Correct 415 ms 86296 KB Output is correct
4 Correct 400 ms 86096 KB Output is correct
5 Correct 33 ms 65624 KB Output is correct
6 Correct 378 ms 82768 KB Output is correct
7 Correct 400 ms 82572 KB Output is correct
8 Correct 426 ms 82992 KB Output is correct
9 Correct 496 ms 83024 KB Output is correct
10 Correct 744 ms 84676 KB Output is correct
11 Correct 740 ms 84048 KB Output is correct
12 Correct 34 ms 65628 KB Output is correct
13 Correct 505 ms 86336 KB Output is correct
14 Correct 1451 ms 90584 KB Output is correct
15 Correct 588 ms 86100 KB Output is correct
16 Correct 603 ms 86096 KB Output is correct
17 Correct 43 ms 65364 KB Output is correct
18 Correct 1090 ms 82752 KB Output is correct
19 Correct 505 ms 82704 KB Output is correct
20 Correct 620 ms 82896 KB Output is correct
21 Correct 583 ms 82756 KB Output is correct
22 Correct 2803 ms 85604 KB Output is correct
23 Execution timed out 3526 ms 86428 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 65616 KB Output is correct
2 Correct 40 ms 66132 KB Output is correct
3 Correct 47 ms 66140 KB Output is correct
4 Correct 48 ms 66344 KB Output is correct
5 Correct 44 ms 66132 KB Output is correct
6 Correct 48 ms 66132 KB Output is correct
7 Correct 39 ms 65628 KB Output is correct
8 Correct 536 ms 83000 KB Output is correct
9 Correct 515 ms 82432 KB Output is correct
10 Correct 33 ms 65624 KB Output is correct
11 Correct 409 ms 86356 KB Output is correct
12 Correct 415 ms 86564 KB Output is correct
13 Correct 417 ms 86284 KB Output is correct
14 Correct 34 ms 65616 KB Output is correct
15 Correct 364 ms 82536 KB Output is correct
16 Correct 454 ms 82512 KB Output is correct
17 Correct 419 ms 83024 KB Output is correct
18 Correct 488 ms 83068 KB Output is correct
19 Correct 741 ms 84820 KB Output is correct
20 Correct 736 ms 84132 KB Output is correct
21 Correct 519 ms 82548 KB Output is correct
22 Correct 536 ms 82564 KB Output is correct
23 Correct 494 ms 83280 KB Output is correct
24 Correct 477 ms 83028 KB Output is correct
25 Correct 519 ms 83424 KB Output is correct
26 Correct 575 ms 82000 KB Output is correct
27 Correct 514 ms 81960 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 65616 KB Output is correct
2 Correct 40 ms 66132 KB Output is correct
3 Correct 47 ms 66140 KB Output is correct
4 Correct 48 ms 66344 KB Output is correct
5 Correct 44 ms 66132 KB Output is correct
6 Correct 48 ms 66132 KB Output is correct
7 Correct 39 ms 65628 KB Output is correct
8 Correct 536 ms 83000 KB Output is correct
9 Correct 515 ms 82432 KB Output is correct
10 Correct 33 ms 65624 KB Output is correct
11 Correct 409 ms 86356 KB Output is correct
12 Correct 415 ms 86564 KB Output is correct
13 Correct 417 ms 86284 KB Output is correct
14 Correct 34 ms 65616 KB Output is correct
15 Correct 364 ms 82536 KB Output is correct
16 Correct 454 ms 82512 KB Output is correct
17 Correct 419 ms 83024 KB Output is correct
18 Correct 488 ms 83068 KB Output is correct
19 Correct 741 ms 84820 KB Output is correct
20 Correct 736 ms 84132 KB Output is correct
21 Correct 519 ms 82548 KB Output is correct
22 Correct 536 ms 82564 KB Output is correct
23 Correct 494 ms 83280 KB Output is correct
24 Correct 477 ms 83028 KB Output is correct
25 Correct 519 ms 83424 KB Output is correct
26 Correct 575 ms 82000 KB Output is correct
27 Correct 514 ms 81960 KB Output is correct
28 Correct 51 ms 65620 KB Output is correct
29 Correct 185 ms 65924 KB Output is correct
30 Correct 317 ms 66152 KB Output is correct
31 Correct 175 ms 66384 KB Output is correct
32 Correct 93 ms 66132 KB Output is correct
33 Correct 246 ms 66132 KB Output is correct
34 Correct 45 ms 65624 KB Output is correct
35 Correct 2803 ms 83080 KB Output is correct
36 Correct 1565 ms 82944 KB Output is correct
37 Correct 1845 ms 82732 KB Output is correct
38 Correct 43 ms 65608 KB Output is correct
39 Correct 498 ms 86096 KB Output is correct
40 Correct 1501 ms 90648 KB Output is correct
41 Correct 580 ms 86036 KB Output is correct
42 Correct 594 ms 86040 KB Output is correct
43 Correct 43 ms 65488 KB Output is correct
44 Correct 1090 ms 82772 KB Output is correct
45 Correct 546 ms 82408 KB Output is correct
46 Correct 706 ms 82768 KB Output is correct
47 Correct 601 ms 83000 KB Output is correct
48 Correct 2827 ms 85720 KB Output is correct
49 Execution timed out 3542 ms 86748 KB Time limit exceeded
50 Halted 0 ms 0 KB -