oj.uz

Submission #911109

# Submission time Handle Problem Language Result Execution time Memory
911109 2024-01-18T13:01:08 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 88664 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 = 600;
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 j = 1; j <= n; j++) {
				for (int k = 0; k <= SZ(adj[j]); k++) {
					dp[j][k] = -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 31 ms 16344 KB Output is correct
2 Correct 35 ms 18972 KB Output is correct
3 Correct 39 ms 19036 KB Output is correct
4 Correct 42 ms 19056 KB Output is correct
5 Correct 34 ms 19024 KB Output is correct
6 Correct 45 ms 19028 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16344 KB Output is correct
2 Correct 35 ms 18972 KB Output is correct
3 Correct 39 ms 19036 KB Output is correct
4 Correct 42 ms 19056 KB Output is correct
5 Correct 34 ms 19024 KB Output is correct
6 Correct 45 ms 19028 KB Output is correct
7 Correct 42 ms 16228 KB Output is correct
8 Correct 315 ms 18956 KB Output is correct
9 Correct 620 ms 19408 KB Output is correct
10 Correct 292 ms 18992 KB Output is correct
11 Correct 201 ms 19040 KB Output is correct
12 Correct 600 ms 19028 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16208 KB Output is correct
2 Correct 286 ms 82544 KB Output is correct
3 Correct 338 ms 82548 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16208 KB Output is correct
2 Correct 286 ms 82544 KB Output is correct
3 Correct 338 ms 82548 KB Output is correct
4 Correct 40 ms 16236 KB Output is correct
5 Correct 1094 ms 87968 KB Output is correct
6 Correct 907 ms 88548 KB Output is correct
7 Correct 1724 ms 88252 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16156 KB Output is correct
2 Correct 299 ms 86408 KB Output is correct
3 Correct 300 ms 86384 KB Output is correct
4 Correct 367 ms 86388 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16156 KB Output is correct
2 Correct 299 ms 86408 KB Output is correct
3 Correct 300 ms 86384 KB Output is correct
4 Correct 367 ms 86388 KB Output is correct
5 Correct 35 ms 16208 KB Output is correct
6 Correct 449 ms 86528 KB Output is correct
7 Correct 1392 ms 86508 KB Output is correct
8 Correct 578 ms 86280 KB Output is correct
9 Correct 583 ms 86612 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16220 KB Output is correct
2 Correct 250 ms 82516 KB Output is correct
3 Correct 326 ms 82432 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16220 KB Output is correct
2 Correct 250 ms 82516 KB Output is correct
3 Correct 326 ms 82432 KB Output is correct
4 Correct 43 ms 16264 KB Output is correct
5 Correct 1656 ms 82848 KB Output is correct
6 Correct 499 ms 82440 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16216 KB Output is correct
2 Correct 282 ms 86196 KB Output is correct
3 Correct 271 ms 86356 KB Output is correct
4 Correct 331 ms 86344 KB Output is correct
5 Correct 28 ms 16208 KB Output is correct
6 Correct 263 ms 83024 KB Output is correct
7 Correct 285 ms 82516 KB Output is correct
8 Correct 296 ms 82996 KB Output is correct
9 Correct 326 ms 82928 KB Output is correct
10 Correct 470 ms 85076 KB Output is correct
11 Correct 471 ms 84172 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16216 KB Output is correct
2 Correct 282 ms 86196 KB Output is correct
3 Correct 271 ms 86356 KB Output is correct
4 Correct 331 ms 86344 KB Output is correct
5 Correct 28 ms 16208 KB Output is correct
6 Correct 263 ms 83024 KB Output is correct
7 Correct 285 ms 82516 KB Output is correct
8 Correct 296 ms 82996 KB Output is correct
9 Correct 326 ms 82928 KB Output is correct
10 Correct 470 ms 85076 KB Output is correct
11 Correct 471 ms 84172 KB Output is correct
12 Correct 31 ms 16212 KB Output is correct
13 Correct 426 ms 86228 KB Output is correct
14 Correct 1326 ms 86208 KB Output is correct
15 Correct 564 ms 86100 KB Output is correct
16 Correct 590 ms 86356 KB Output is correct
17 Correct 38 ms 16220 KB Output is correct
18 Correct 1647 ms 82868 KB Output is correct
19 Correct 516 ms 82372 KB Output is correct
20 Correct 712 ms 83280 KB Output is correct
21 Correct 574 ms 82772 KB Output is correct
22 Correct 3160 ms 84100 KB Output is correct
23 Execution timed out 3523 ms 85216 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16208 KB Output is correct
2 Correct 39 ms 18740 KB Output is correct
3 Correct 39 ms 19024 KB Output is correct
4 Correct 37 ms 19136 KB Output is correct
5 Correct 34 ms 19036 KB Output is correct
6 Correct 42 ms 19020 KB Output is correct
7 Correct 32 ms 16220 KB Output is correct
8 Correct 285 ms 82376 KB Output is correct
9 Correct 296 ms 82704 KB Output is correct
10 Correct 27 ms 16212 KB Output is correct
11 Correct 270 ms 86392 KB Output is correct
12 Correct 277 ms 86352 KB Output is correct
13 Correct 327 ms 86356 KB Output is correct
14 Correct 29 ms 16220 KB Output is correct
15 Correct 256 ms 82512 KB Output is correct
16 Correct 294 ms 82448 KB Output is correct
17 Correct 291 ms 83272 KB Output is correct
18 Correct 313 ms 83044 KB Output is correct
19 Correct 462 ms 84796 KB Output is correct
20 Correct 460 ms 84400 KB Output is correct
21 Correct 295 ms 82760 KB Output is correct
22 Correct 317 ms 82700 KB Output is correct
23 Correct 313 ms 83284 KB Output is correct
24 Correct 307 ms 83548 KB Output is correct
25 Correct 323 ms 83204 KB Output is correct
26 Correct 352 ms 82256 KB Output is correct
27 Correct 318 ms 82128 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16208 KB Output is correct
2 Correct 39 ms 18740 KB Output is correct
3 Correct 39 ms 19024 KB Output is correct
4 Correct 37 ms 19136 KB Output is correct
5 Correct 34 ms 19036 KB Output is correct
6 Correct 42 ms 19020 KB Output is correct
7 Correct 32 ms 16220 KB Output is correct
8 Correct 285 ms 82376 KB Output is correct
9 Correct 296 ms 82704 KB Output is correct
10 Correct 27 ms 16212 KB Output is correct
11 Correct 270 ms 86392 KB Output is correct
12 Correct 277 ms 86352 KB Output is correct
13 Correct 327 ms 86356 KB Output is correct
14 Correct 29 ms 16220 KB Output is correct
15 Correct 256 ms 82512 KB Output is correct
16 Correct 294 ms 82448 KB Output is correct
17 Correct 291 ms 83272 KB Output is correct
18 Correct 313 ms 83044 KB Output is correct
19 Correct 462 ms 84796 KB Output is correct
20 Correct 460 ms 84400 KB Output is correct
21 Correct 295 ms 82760 KB Output is correct
22 Correct 317 ms 82700 KB Output is correct
23 Correct 313 ms 83284 KB Output is correct
24 Correct 307 ms 83548 KB Output is correct
25 Correct 323 ms 83204 KB Output is correct
26 Correct 352 ms 82256 KB Output is correct
27 Correct 318 ms 82128 KB Output is correct
28 Correct 47 ms 16348 KB Output is correct
29 Correct 290 ms 18768 KB Output is correct
30 Correct 623 ms 19280 KB Output is correct
31 Correct 285 ms 18960 KB Output is correct
32 Correct 208 ms 19284 KB Output is correct
33 Correct 589 ms 19024 KB Output is correct
34 Correct 41 ms 16212 KB Output is correct
35 Correct 935 ms 88248 KB Output is correct
36 Correct 892 ms 88664 KB Output is correct
37 Correct 1342 ms 88236 KB Output is correct
38 Correct 30 ms 16260 KB Output is correct
39 Correct 455 ms 86096 KB Output is correct
40 Correct 1304 ms 86396 KB Output is correct
41 Correct 581 ms 86096 KB Output is correct
42 Correct 588 ms 85948 KB Output is correct
43 Correct 38 ms 16380 KB Output is correct
44 Correct 1626 ms 82932 KB Output is correct
45 Correct 515 ms 82436 KB Output is correct
46 Correct 716 ms 83296 KB Output is correct
47 Correct 542 ms 82964 KB Output is correct
48 Correct 3117 ms 84528 KB Output is correct
49 Execution timed out 3556 ms 85012 KB Time limit exceeded
50 Halted 0 ms 0 KB -