oj.uz

Submission #911108

# Submission time Handle Problem Language Result Execution time Memory
911108 2024-01-18T13:00:09 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 88968 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 = 580;
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 16208 KB Output is correct
2 Correct 36 ms 18836 KB Output is correct
3 Correct 41 ms 19024 KB Output is correct
4 Correct 39 ms 19400 KB Output is correct
5 Correct 34 ms 19124 KB Output is correct
6 Correct 44 ms 19028 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16208 KB Output is correct
2 Correct 36 ms 18836 KB Output is correct
3 Correct 41 ms 19024 KB Output is correct
4 Correct 39 ms 19400 KB Output is correct
5 Correct 34 ms 19124 KB Output is correct
6 Correct 44 ms 19028 KB Output is correct
7 Correct 45 ms 16212 KB Output is correct
8 Correct 300 ms 19172 KB Output is correct
9 Correct 635 ms 19052 KB Output is correct
10 Correct 279 ms 18972 KB Output is correct
11 Correct 256 ms 19024 KB Output is correct
12 Correct 717 ms 19336 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16212 KB Output is correct
2 Correct 290 ms 82420 KB Output is correct
3 Correct 314 ms 82436 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16212 KB Output is correct
2 Correct 290 ms 82420 KB Output is correct
3 Correct 314 ms 82436 KB Output is correct
4 Correct 44 ms 16380 KB Output is correct
5 Correct 889 ms 88088 KB Output is correct
6 Correct 906 ms 88968 KB Output is correct
7 Correct 1611 ms 88232 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16220 KB Output is correct
2 Correct 267 ms 86232 KB Output is correct
3 Correct 279 ms 86444 KB Output is correct
4 Correct 350 ms 86356 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16220 KB Output is correct
2 Correct 267 ms 86232 KB Output is correct
3 Correct 279 ms 86444 KB Output is correct
4 Correct 350 ms 86356 KB Output is correct
5 Correct 30 ms 16220 KB Output is correct
6 Correct 442 ms 86260 KB Output is correct
7 Correct 1382 ms 86380 KB Output is correct
8 Correct 547 ms 86100 KB Output is correct
9 Correct 559 ms 86328 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 16464 KB Output is correct
2 Correct 244 ms 82492 KB Output is correct
3 Correct 301 ms 82528 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 16464 KB Output is correct
2 Correct 244 ms 82492 KB Output is correct
3 Correct 301 ms 82528 KB Output is correct
4 Correct 38 ms 16212 KB Output is correct
5 Correct 1510 ms 82812 KB Output is correct
6 Correct 498 ms 82516 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16208 KB Output is correct
2 Correct 277 ms 86352 KB Output is correct
3 Correct 277 ms 86292 KB Output is correct
4 Correct 324 ms 86352 KB Output is correct
5 Correct 28 ms 16220 KB Output is correct
6 Correct 249 ms 82532 KB Output is correct
7 Correct 281 ms 82516 KB Output is correct
8 Correct 278 ms 83020 KB Output is correct
9 Correct 330 ms 83028 KB Output is correct
10 Correct 442 ms 84632 KB Output is correct
11 Correct 469 ms 84048 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16208 KB Output is correct
2 Correct 277 ms 86352 KB Output is correct
3 Correct 277 ms 86292 KB Output is correct
4 Correct 324 ms 86352 KB Output is correct
5 Correct 28 ms 16220 KB Output is correct
6 Correct 249 ms 82532 KB Output is correct
7 Correct 281 ms 82516 KB Output is correct
8 Correct 278 ms 83020 KB Output is correct
9 Correct 330 ms 83028 KB Output is correct
10 Correct 442 ms 84632 KB Output is correct
11 Correct 469 ms 84048 KB Output is correct
12 Correct 30 ms 16208 KB Output is correct
13 Correct 440 ms 86236 KB Output is correct
14 Correct 1326 ms 86548 KB Output is correct
15 Correct 647 ms 85988 KB Output is correct
16 Correct 540 ms 86004 KB Output is correct
17 Correct 38 ms 16220 KB Output is correct
18 Correct 1540 ms 82700 KB Output is correct
19 Correct 501 ms 82676 KB Output is correct
20 Correct 651 ms 83028 KB Output is correct
21 Correct 536 ms 82772 KB Output is correct
22 Correct 3088 ms 84252 KB Output is correct
23 Execution timed out 3561 ms 86628 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 16220 KB Output is correct
2 Correct 38 ms 18768 KB Output is correct
3 Correct 39 ms 19024 KB Output is correct
4 Correct 37 ms 19028 KB Output is correct
5 Correct 34 ms 19028 KB Output is correct
6 Correct 43 ms 18960 KB Output is correct
7 Correct 33 ms 16208 KB Output is correct
8 Correct 294 ms 82584 KB Output is correct
9 Correct 306 ms 82552 KB Output is correct
10 Correct 28 ms 16212 KB Output is correct
11 Correct 275 ms 86180 KB Output is correct
12 Correct 268 ms 86396 KB Output is correct
13 Correct 340 ms 86356 KB Output is correct
14 Correct 29 ms 16220 KB Output is correct
15 Correct 248 ms 82716 KB Output is correct
16 Correct 286 ms 82792 KB Output is correct
17 Correct 292 ms 82972 KB Output is correct
18 Correct 333 ms 83024 KB Output is correct
19 Correct 445 ms 84872 KB Output is correct
20 Correct 457 ms 84272 KB Output is correct
21 Correct 286 ms 82516 KB Output is correct
22 Correct 303 ms 82552 KB Output is correct
23 Correct 311 ms 83120 KB Output is correct
24 Correct 305 ms 83256 KB Output is correct
25 Correct 319 ms 83208 KB Output is correct
26 Correct 340 ms 81956 KB Output is correct
27 Correct 315 ms 82004 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16220 KB Output is correct
2 Correct 38 ms 18768 KB Output is correct
3 Correct 39 ms 19024 KB Output is correct
4 Correct 37 ms 19028 KB Output is correct
5 Correct 34 ms 19028 KB Output is correct
6 Correct 43 ms 18960 KB Output is correct
7 Correct 33 ms 16208 KB Output is correct
8 Correct 294 ms 82584 KB Output is correct
9 Correct 306 ms 82552 KB Output is correct
10 Correct 28 ms 16212 KB Output is correct
11 Correct 275 ms 86180 KB Output is correct
12 Correct 268 ms 86396 KB Output is correct
13 Correct 340 ms 86356 KB Output is correct
14 Correct 29 ms 16220 KB Output is correct
15 Correct 248 ms 82716 KB Output is correct
16 Correct 286 ms 82792 KB Output is correct
17 Correct 292 ms 82972 KB Output is correct
18 Correct 333 ms 83024 KB Output is correct
19 Correct 445 ms 84872 KB Output is correct
20 Correct 457 ms 84272 KB Output is correct
21 Correct 286 ms 82516 KB Output is correct
22 Correct 303 ms 82552 KB Output is correct
23 Correct 311 ms 83120 KB Output is correct
24 Correct 305 ms 83256 KB Output is correct
25 Correct 319 ms 83208 KB Output is correct
26 Correct 340 ms 81956 KB Output is correct
27 Correct 315 ms 82004 KB Output is correct
28 Correct 41 ms 16220 KB Output is correct
29 Correct 293 ms 18776 KB Output is correct
30 Correct 630 ms 19028 KB Output is correct
31 Correct 272 ms 18768 KB Output is correct
32 Correct 252 ms 19008 KB Output is correct
33 Correct 707 ms 19404 KB Output is correct
34 Correct 40 ms 16220 KB Output is correct
35 Correct 930 ms 88188 KB Output is correct
36 Correct 886 ms 88328 KB Output is correct
37 Correct 1431 ms 88184 KB Output is correct
38 Correct 28 ms 16208 KB Output is correct
39 Correct 435 ms 86352 KB Output is correct
40 Correct 1327 ms 86304 KB Output is correct
41 Correct 606 ms 86124 KB Output is correct
42 Correct 575 ms 86100 KB Output is correct
43 Correct 39 ms 16328 KB Output is correct
44 Correct 1525 ms 82604 KB Output is correct
45 Correct 487 ms 82528 KB Output is correct
46 Correct 674 ms 82952 KB Output is correct
47 Correct 621 ms 83100 KB Output is correct
48 Correct 3370 ms 83996 KB Output is correct
49 Execution timed out 3514 ms 85292 KB Time limit exceeded
50 Halted 0 ms 0 KB -