oj.uz

Submission #910142

# Submission time Handle Problem Language Result Execution time Memory
910142 2024-01-18T00:08:09 Z MinaRagy06 Inside information (BOI21_servers) C++17
67.5 / 100
 3500 ms 90304 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[N][18][2];
int st[N], en[N], curt;
void dfs(int i, int par, int part) {
	bl[i][0][0] = {par, part, part};
	bl[i][0][1] = {par, part, part};
	for (int j = 1; j < 18; j++) {
		{
			bl[i][j][0] = bl[i][j - 1][0];
			auto [lst, lstt, mx] = bl[i][j][0];
			if (lstt <= bl[lst][0][0][1]) {
				bl[i][j][0] = bl[lst][j - 1][0];
				bl[i][j][0][2] = max(bl[i][j][0][2], mx);
			}
		}
		{
			bl[i][j][1] = bl[i][j - 1][1];
			auto [lst, lstt, mx] = bl[i][j][1];
			if (lstt >= bl[lst][0][1][1]) {
				bl[i][j][1] = bl[lst][j - 1][1];
				bl[i][j][1][2] = max(bl[i][j][1][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[a][17][t][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[a][j][t][0], b)) {
			mx = max(mx, bl[a][j][t][2]);
			a = bl[a][j][t][0];
		}
	}
	return {max(mx, bl[a][0][t][2]), bl[a][0][t][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:88:7: warning: unused variable 'S' [-Wunused-variable]
   88 |  auto S = chrono::steady_clock::now().time_since_epoch().count();
      |       ^
servers.cpp:121:5: warning: unused variable 's' [-Wunused-variable]
  121 |  ll s = 0;
      |     ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 16208 KB Output is correct
2 Correct 34 ms 18916 KB Output is correct
3 Correct 41 ms 19096 KB Output is correct
4 Correct 58 ms 18832 KB Output is correct
5 Correct 37 ms 19024 KB Output is correct
6 Correct 47 ms 19024 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 16208 KB Output is correct
2 Correct 34 ms 18916 KB Output is correct
3 Correct 41 ms 19096 KB Output is correct
4 Correct 58 ms 18832 KB Output is correct
5 Correct 37 ms 19024 KB Output is correct
6 Correct 47 ms 19024 KB Output is correct
7 Correct 57 ms 16200 KB Output is correct
8 Correct 200 ms 18768 KB Output is correct
9 Correct 340 ms 18976 KB Output is correct
10 Correct 195 ms 18768 KB Output is correct
11 Correct 99 ms 19028 KB Output is correct
12 Correct 280 ms 19076 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16220 KB Output is correct
2 Correct 523 ms 82552 KB Output is correct
3 Correct 384 ms 82524 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16220 KB Output is correct
2 Correct 523 ms 82552 KB Output is correct
3 Correct 384 ms 82524 KB Output is correct
4 Correct 40 ms 16352 KB Output is correct
5 Execution timed out 3522 ms 82692 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16212 KB Output is correct
2 Correct 446 ms 86476 KB Output is correct
3 Correct 440 ms 86352 KB Output is correct
4 Correct 519 ms 86492 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16212 KB Output is correct
2 Correct 446 ms 86476 KB Output is correct
3 Correct 440 ms 86352 KB Output is correct
4 Correct 519 ms 86492 KB Output is correct
5 Correct 30 ms 16304 KB Output is correct
6 Correct 612 ms 86428 KB Output is correct
7 Correct 1787 ms 90076 KB Output is correct
8 Correct 794 ms 86032 KB Output is correct
9 Correct 758 ms 86172 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16364 KB Output is correct
2 Correct 366 ms 82356 KB Output is correct
3 Correct 577 ms 82376 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16364 KB Output is correct
2 Correct 366 ms 82356 KB Output is correct
3 Correct 577 ms 82376 KB Output is correct
4 Correct 40 ms 16468 KB Output is correct
5 Correct 1277 ms 82628 KB Output is correct
6 Correct 605 ms 82496 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16188 KB Output is correct
2 Correct 446 ms 86628 KB Output is correct
3 Correct 486 ms 86220 KB Output is correct
4 Correct 554 ms 86304 KB Output is correct
5 Correct 41 ms 16220 KB Output is correct
6 Correct 362 ms 82516 KB Output is correct
7 Correct 375 ms 82516 KB Output is correct
8 Correct 475 ms 82960 KB Output is correct
9 Correct 521 ms 83052 KB Output is correct
10 Correct 761 ms 84864 KB Output is correct
11 Correct 732 ms 84136 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16188 KB Output is correct
2 Correct 446 ms 86628 KB Output is correct
3 Correct 486 ms 86220 KB Output is correct
4 Correct 554 ms 86304 KB Output is correct
5 Correct 41 ms 16220 KB Output is correct
6 Correct 362 ms 82516 KB Output is correct
7 Correct 375 ms 82516 KB Output is correct
8 Correct 475 ms 82960 KB Output is correct
9 Correct 521 ms 83052 KB Output is correct
10 Correct 761 ms 84864 KB Output is correct
11 Correct 732 ms 84136 KB Output is correct
12 Correct 38 ms 16232 KB Output is correct
13 Correct 605 ms 86252 KB Output is correct
14 Correct 1820 ms 90304 KB Output is correct
15 Correct 614 ms 86032 KB Output is correct
16 Correct 704 ms 86332 KB Output is correct
17 Correct 38 ms 16180 KB Output is correct
18 Correct 1436 ms 82428 KB Output is correct
19 Correct 611 ms 82748 KB Output is correct
20 Correct 706 ms 82768 KB Output is correct
21 Correct 630 ms 83004 KB Output is correct
22 Correct 3002 ms 85684 KB Output is correct
23 Execution timed out 3545 ms 86168 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16224 KB Output is correct
2 Correct 36 ms 18956 KB Output is correct
3 Correct 45 ms 19048 KB Output is correct
4 Correct 39 ms 19008 KB Output is correct
5 Correct 34 ms 19028 KB Output is correct
6 Correct 48 ms 19024 KB Output is correct
7 Correct 31 ms 16244 KB Output is correct
8 Correct 418 ms 82552 KB Output is correct
9 Correct 403 ms 82688 KB Output is correct
10 Correct 25 ms 16216 KB Output is correct
11 Correct 417 ms 86356 KB Output is correct
12 Correct 410 ms 86332 KB Output is correct
13 Correct 480 ms 86212 KB Output is correct
14 Correct 44 ms 16284 KB Output is correct
15 Correct 366 ms 82512 KB Output is correct
16 Correct 451 ms 82440 KB Output is correct
17 Correct 446 ms 82956 KB Output is correct
18 Correct 455 ms 82944 KB Output is correct
19 Correct 724 ms 84832 KB Output is correct
20 Correct 673 ms 84436 KB Output is correct
21 Correct 433 ms 82364 KB Output is correct
22 Correct 440 ms 82484 KB Output is correct
23 Correct 515 ms 83244 KB Output is correct
24 Correct 495 ms 83152 KB Output is correct
25 Correct 443 ms 83160 KB Output is correct
26 Correct 517 ms 82132 KB Output is correct
27 Correct 492 ms 82076 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16224 KB Output is correct
2 Correct 36 ms 18956 KB Output is correct
3 Correct 45 ms 19048 KB Output is correct
4 Correct 39 ms 19008 KB Output is correct
5 Correct 34 ms 19028 KB Output is correct
6 Correct 48 ms 19024 KB Output is correct
7 Correct 31 ms 16244 KB Output is correct
8 Correct 418 ms 82552 KB Output is correct
9 Correct 403 ms 82688 KB Output is correct
10 Correct 25 ms 16216 KB Output is correct
11 Correct 417 ms 86356 KB Output is correct
12 Correct 410 ms 86332 KB Output is correct
13 Correct 480 ms 86212 KB Output is correct
14 Correct 44 ms 16284 KB Output is correct
15 Correct 366 ms 82512 KB Output is correct
16 Correct 451 ms 82440 KB Output is correct
17 Correct 446 ms 82956 KB Output is correct
18 Correct 455 ms 82944 KB Output is correct
19 Correct 724 ms 84832 KB Output is correct
20 Correct 673 ms 84436 KB Output is correct
21 Correct 433 ms 82364 KB Output is correct
22 Correct 440 ms 82484 KB Output is correct
23 Correct 515 ms 83244 KB Output is correct
24 Correct 495 ms 83152 KB Output is correct
25 Correct 443 ms 83160 KB Output is correct
26 Correct 517 ms 82132 KB Output is correct
27 Correct 492 ms 82076 KB Output is correct
28 Correct 41 ms 16220 KB Output is correct
29 Correct 164 ms 18900 KB Output is correct
30 Correct 335 ms 19536 KB Output is correct
31 Correct 177 ms 18948 KB Output is correct
32 Correct 119 ms 18916 KB Output is correct
33 Correct 239 ms 19156 KB Output is correct
34 Correct 65 ms 16284 KB Output is correct
35 Execution timed out 3581 ms 82516 KB Time limit exceeded
36 Halted 0 ms 0 KB -