oj.uz

Submission #910179

# Submission time Handle Problem Language Result Execution time Memory
910179 2024-01-18T01:04:09 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 88496 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, LOG = 18;
vector<array<int, 3>> adj[N];
//0: increasing, 1: decreasing, {ancestor, last weight}
array<int, 3> bl[N][LOG][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 < LOG; 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][LOG - 1][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 = LOG - 1; 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 j = (par == SZ(adj[i])? 0 : par + 1);
	dp[i][par] = 1;
	if (j < SZ(adj[i])) {
		if (adj[i][j][1] > lst) return dp[i][par];
		dp[i][par] += solve(adj[i][j][0], adj[i][j][2]) + solve(i, j) - 1;
	}
	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) {
			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
			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)) {
					array<int, 2> val = check(0, x, b);
					ans += val[0] <= t - 1;
				} else if (isanc(a, x)) {
					array<int, 2> val = check(0, x, a);
					ans += val[0] <= t - 1;
				} else {
					ans += checkpath(x, a, t - 1, 0);
				}
			}
#ifdef MINA
			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\n";
#endif
	return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:85:7: warning: unused variable 'S' [-Wunused-variable]
   85 |  auto S = chrono::steady_clock::now().time_since_epoch().count();
      |       ^
servers.cpp:118:5: warning: unused variable 's' [-Wunused-variable]
  118 |  ll s = 0;
      |     ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 16220 KB Output is correct
2 Correct 37 ms 18824 KB Output is correct
3 Correct 42 ms 18988 KB Output is correct
4 Correct 36 ms 18816 KB Output is correct
5 Correct 40 ms 19024 KB Output is correct
6 Correct 42 ms 18908 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 16220 KB Output is correct
2 Correct 37 ms 18824 KB Output is correct
3 Correct 42 ms 18988 KB Output is correct
4 Correct 36 ms 18816 KB Output is correct
5 Correct 40 ms 19024 KB Output is correct
6 Correct 42 ms 18908 KB Output is correct
7 Correct 41 ms 16228 KB Output is correct
8 Correct 219 ms 18824 KB Output is correct
9 Correct 375 ms 19028 KB Output is correct
10 Correct 191 ms 18972 KB Output is correct
11 Correct 98 ms 18868 KB Output is correct
12 Correct 283 ms 19212 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16212 KB Output is correct
2 Correct 415 ms 82512 KB Output is correct
3 Correct 352 ms 82488 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16212 KB Output is correct
2 Correct 415 ms 82512 KB Output is correct
3 Correct 352 ms 82488 KB Output is correct
4 Correct 42 ms 16348 KB Output is correct
5 Correct 1300 ms 88440 KB Output is correct
6 Correct 1211 ms 88496 KB Output is correct
7 Correct 1894 ms 88372 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16216 KB Output is correct
2 Correct 365 ms 86368 KB Output is correct
3 Correct 369 ms 86608 KB Output is correct
4 Correct 395 ms 86280 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16216 KB Output is correct
2 Correct 365 ms 86368 KB Output is correct
3 Correct 369 ms 86608 KB Output is correct
4 Correct 395 ms 86280 KB Output is correct
5 Correct 29 ms 16216 KB Output is correct
6 Correct 470 ms 86236 KB Output is correct
7 Correct 1489 ms 86312 KB Output is correct
8 Correct 533 ms 86176 KB Output is correct
9 Correct 534 ms 86140 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16216 KB Output is correct
2 Correct 313 ms 82424 KB Output is correct
3 Correct 417 ms 82532 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16216 KB Output is correct
2 Correct 313 ms 82424 KB Output is correct
3 Correct 417 ms 82532 KB Output is correct
4 Correct 37 ms 16212 KB Output is correct
5 Correct 1208 ms 82480 KB Output is correct
6 Correct 494 ms 82456 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16220 KB Output is correct
2 Correct 345 ms 86236 KB Output is correct
3 Correct 342 ms 86368 KB Output is correct
4 Correct 398 ms 86136 KB Output is correct
5 Correct 27 ms 16212 KB Output is correct
6 Correct 305 ms 82380 KB Output is correct
7 Correct 362 ms 82512 KB Output is correct
8 Correct 337 ms 82940 KB Output is correct
9 Correct 406 ms 82944 KB Output is correct
10 Correct 598 ms 84560 KB Output is correct
11 Correct 579 ms 84052 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16220 KB Output is correct
2 Correct 345 ms 86236 KB Output is correct
3 Correct 342 ms 86368 KB Output is correct
4 Correct 398 ms 86136 KB Output is correct
5 Correct 27 ms 16212 KB Output is correct
6 Correct 305 ms 82380 KB Output is correct
7 Correct 362 ms 82512 KB Output is correct
8 Correct 337 ms 82940 KB Output is correct
9 Correct 406 ms 82944 KB Output is correct
10 Correct 598 ms 84560 KB Output is correct
11 Correct 579 ms 84052 KB Output is correct
12 Correct 39 ms 16216 KB Output is correct
13 Correct 473 ms 86124 KB Output is correct
14 Correct 1358 ms 86568 KB Output is correct
15 Correct 532 ms 86352 KB Output is correct
16 Correct 583 ms 85936 KB Output is correct
17 Correct 43 ms 16360 KB Output is correct
18 Correct 1151 ms 82780 KB Output is correct
19 Correct 514 ms 82540 KB Output is correct
20 Correct 699 ms 82952 KB Output is correct
21 Correct 580 ms 82948 KB Output is correct
22 Correct 2937 ms 83984 KB Output is correct
23 Execution timed out 3526 ms 85080 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16220 KB Output is correct
2 Correct 35 ms 18752 KB Output is correct
3 Correct 40 ms 19036 KB Output is correct
4 Correct 38 ms 19024 KB Output is correct
5 Correct 34 ms 19036 KB Output is correct
6 Correct 41 ms 19024 KB Output is correct
7 Correct 33 ms 16220 KB Output is correct
8 Correct 419 ms 82576 KB Output is correct
9 Correct 406 ms 82652 KB Output is correct
10 Correct 31 ms 16212 KB Output is correct
11 Correct 345 ms 86280 KB Output is correct
12 Correct 379 ms 86408 KB Output is correct
13 Correct 365 ms 86100 KB Output is correct
14 Correct 29 ms 16208 KB Output is correct
15 Correct 329 ms 82512 KB Output is correct
16 Correct 338 ms 82516 KB Output is correct
17 Correct 366 ms 82988 KB Output is correct
18 Correct 462 ms 83188 KB Output is correct
19 Correct 607 ms 84560 KB Output is correct
20 Correct 622 ms 84332 KB Output is correct
21 Correct 376 ms 82364 KB Output is correct
22 Correct 456 ms 82552 KB Output is correct
23 Correct 439 ms 83284 KB Output is correct
24 Correct 389 ms 83584 KB Output is correct
25 Correct 388 ms 83256 KB Output is correct
26 Correct 479 ms 82096 KB Output is correct
27 Correct 448 ms 82000 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16220 KB Output is correct
2 Correct 35 ms 18752 KB Output is correct
3 Correct 40 ms 19036 KB Output is correct
4 Correct 38 ms 19024 KB Output is correct
5 Correct 34 ms 19036 KB Output is correct
6 Correct 41 ms 19024 KB Output is correct
7 Correct 33 ms 16220 KB Output is correct
8 Correct 419 ms 82576 KB Output is correct
9 Correct 406 ms 82652 KB Output is correct
10 Correct 31 ms 16212 KB Output is correct
11 Correct 345 ms 86280 KB Output is correct
12 Correct 379 ms 86408 KB Output is correct
13 Correct 365 ms 86100 KB Output is correct
14 Correct 29 ms 16208 KB Output is correct
15 Correct 329 ms 82512 KB Output is correct
16 Correct 338 ms 82516 KB Output is correct
17 Correct 366 ms 82988 KB Output is correct
18 Correct 462 ms 83188 KB Output is correct
19 Correct 607 ms 84560 KB Output is correct
20 Correct 622 ms 84332 KB Output is correct
21 Correct 376 ms 82364 KB Output is correct
22 Correct 456 ms 82552 KB Output is correct
23 Correct 439 ms 83284 KB Output is correct
24 Correct 389 ms 83584 KB Output is correct
25 Correct 388 ms 83256 KB Output is correct
26 Correct 479 ms 82096 KB Output is correct
27 Correct 448 ms 82000 KB Output is correct
28 Correct 43 ms 16208 KB Output is correct
29 Correct 196 ms 18848 KB Output is correct
30 Correct 401 ms 18980 KB Output is correct
31 Correct 193 ms 18932 KB Output is correct
32 Correct 131 ms 19112 KB Output is correct
33 Correct 344 ms 19148 KB Output is correct
34 Correct 41 ms 16220 KB Output is correct
35 Correct 2092 ms 88168 KB Output is correct
36 Correct 2178 ms 88440 KB Output is correct
37 Correct 1681 ms 88152 KB Output is correct
38 Correct 29 ms 16328 KB Output is correct
39 Correct 496 ms 86236 KB Output is correct
40 Correct 1541 ms 86536 KB Output is correct
41 Correct 580 ms 86084 KB Output is correct
42 Correct 547 ms 86152 KB Output is correct
43 Correct 38 ms 16232 KB Output is correct
44 Correct 1236 ms 82828 KB Output is correct
45 Correct 549 ms 82516 KB Output is correct
46 Correct 620 ms 82892 KB Output is correct
47 Correct 575 ms 83024 KB Output is correct
48 Correct 2672 ms 84360 KB Output is correct
49 Execution timed out 3534 ms 84892 KB Time limit exceeded
50 Halted 0 ms 0 KB -