oj.uz

Submission #910154

# Submission time Handle Problem Language Result Execution time Memory
910154 2024-01-18T00:30:08 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 88640 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];
	dp[i][par] = 1;
	for (int j = (par == SZ(adj[i])? 0 : par + 1); j < SZ(adj[i]); j++) {
		auto [nxt, t, nxtidx] = adj[i][j];
		if (t > lst) break;
		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 = 380;
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)) {
					array<int, 2> val = check(0, x, b);
					ans += val[0] <= t - 1;
				} 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: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 34 ms 18776 KB Output is correct
3 Correct 40 ms 19024 KB Output is correct
4 Correct 36 ms 19032 KB Output is correct
5 Correct 34 ms 18988 KB Output is correct
6 Correct 41 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 34 ms 18776 KB Output is correct
3 Correct 40 ms 19024 KB Output is correct
4 Correct 36 ms 19032 KB Output is correct
5 Correct 34 ms 18988 KB Output is correct
6 Correct 41 ms 19028 KB Output is correct
7 Correct 43 ms 16216 KB Output is correct
8 Correct 196 ms 18772 KB Output is correct
9 Correct 428 ms 19024 KB Output is correct
10 Correct 213 ms 19008 KB Output is correct
11 Correct 133 ms 18868 KB Output is correct
12 Correct 418 ms 19180 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16464 KB Output is correct
2 Correct 332 ms 82440 KB Output is correct
3 Correct 342 ms 82436 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16464 KB Output is correct
2 Correct 332 ms 82440 KB Output is correct
3 Correct 342 ms 82436 KB Output is correct
4 Correct 45 ms 16388 KB Output is correct
5 Correct 1328 ms 82596 KB Output is correct
6 Correct 708 ms 82692 KB Output is correct
7 Correct 1084 ms 82868 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16208 KB Output is correct
2 Correct 303 ms 86328 KB Output is correct
3 Correct 317 ms 86468 KB Output is correct
4 Correct 375 ms 86264 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16208 KB Output is correct
2 Correct 303 ms 86328 KB Output is correct
3 Correct 317 ms 86468 KB Output is correct
4 Correct 375 ms 86264 KB Output is correct
5 Correct 29 ms 16208 KB Output is correct
6 Correct 434 ms 86156 KB Output is correct
7 Correct 1326 ms 86896 KB Output is correct
8 Correct 556 ms 86040 KB Output is correct
9 Correct 543 ms 86252 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16212 KB Output is correct
2 Correct 283 ms 82516 KB Output is correct
3 Correct 316 ms 82516 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16212 KB Output is correct
2 Correct 283 ms 82516 KB Output is correct
3 Correct 316 ms 82516 KB Output is correct
4 Correct 39 ms 16220 KB Output is correct
5 Correct 1078 ms 82548 KB Output is correct
6 Correct 457 ms 82516 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 334 ms 86356 KB Output is correct
3 Correct 311 ms 86372 KB Output is correct
4 Correct 399 ms 86236 KB Output is correct
5 Correct 28 ms 16300 KB Output is correct
6 Correct 297 ms 82548 KB Output is correct
7 Correct 377 ms 82512 KB Output is correct
8 Correct 380 ms 82996 KB Output is correct
9 Correct 411 ms 83024 KB Output is correct
10 Correct 620 ms 84504 KB Output is correct
11 Correct 615 ms 84080 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 334 ms 86356 KB Output is correct
3 Correct 311 ms 86372 KB Output is correct
4 Correct 399 ms 86236 KB Output is correct
5 Correct 28 ms 16300 KB Output is correct
6 Correct 297 ms 82548 KB Output is correct
7 Correct 377 ms 82512 KB Output is correct
8 Correct 380 ms 82996 KB Output is correct
9 Correct 411 ms 83024 KB Output is correct
10 Correct 620 ms 84504 KB Output is correct
11 Correct 615 ms 84080 KB Output is correct
12 Correct 31 ms 16316 KB Output is correct
13 Correct 505 ms 86400 KB Output is correct
14 Correct 1454 ms 87084 KB Output is correct
15 Correct 583 ms 86232 KB Output is correct
16 Correct 571 ms 86168 KB Output is correct
17 Correct 43 ms 16216 KB Output is correct
18 Correct 1152 ms 82600 KB Output is correct
19 Correct 529 ms 82644 KB Output is correct
20 Correct 615 ms 83236 KB Output is correct
21 Correct 570 ms 83004 KB Output is correct
22 Correct 2738 ms 84796 KB Output is correct
23 Execution timed out 3595 ms 87088 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16976 KB Output is correct
2 Correct 36 ms 20060 KB Output is correct
3 Correct 43 ms 19996 KB Output is correct
4 Correct 41 ms 20052 KB Output is correct
5 Correct 35 ms 20048 KB Output is correct
6 Correct 41 ms 20060 KB Output is correct
7 Correct 32 ms 16988 KB Output is correct
8 Correct 338 ms 84224 KB Output is correct
9 Correct 373 ms 84640 KB Output is correct
10 Correct 41 ms 16984 KB Output is correct
11 Correct 349 ms 88404 KB Output is correct
12 Correct 353 ms 88436 KB Output is correct
13 Correct 381 ms 88144 KB Output is correct
14 Correct 28 ms 16764 KB Output is correct
15 Correct 287 ms 84532 KB Output is correct
16 Correct 359 ms 84676 KB Output is correct
17 Correct 399 ms 85080 KB Output is correct
18 Correct 392 ms 84912 KB Output is correct
19 Correct 569 ms 87416 KB Output is correct
20 Correct 543 ms 86280 KB Output is correct
21 Correct 389 ms 84872 KB Output is correct
22 Correct 355 ms 85120 KB Output is correct
23 Correct 360 ms 85204 KB Output is correct
24 Correct 345 ms 85328 KB Output is correct
25 Correct 350 ms 85256 KB Output is correct
26 Correct 414 ms 84304 KB Output is correct
27 Correct 393 ms 84304 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16976 KB Output is correct
2 Correct 36 ms 20060 KB Output is correct
3 Correct 43 ms 19996 KB Output is correct
4 Correct 41 ms 20052 KB Output is correct
5 Correct 35 ms 20048 KB Output is correct
6 Correct 41 ms 20060 KB Output is correct
7 Correct 32 ms 16988 KB Output is correct
8 Correct 338 ms 84224 KB Output is correct
9 Correct 373 ms 84640 KB Output is correct
10 Correct 41 ms 16984 KB Output is correct
11 Correct 349 ms 88404 KB Output is correct
12 Correct 353 ms 88436 KB Output is correct
13 Correct 381 ms 88144 KB Output is correct
14 Correct 28 ms 16764 KB Output is correct
15 Correct 287 ms 84532 KB Output is correct
16 Correct 359 ms 84676 KB Output is correct
17 Correct 399 ms 85080 KB Output is correct
18 Correct 392 ms 84912 KB Output is correct
19 Correct 569 ms 87416 KB Output is correct
20 Correct 543 ms 86280 KB Output is correct
21 Correct 389 ms 84872 KB Output is correct
22 Correct 355 ms 85120 KB Output is correct
23 Correct 360 ms 85204 KB Output is correct
24 Correct 345 ms 85328 KB Output is correct
25 Correct 350 ms 85256 KB Output is correct
26 Correct 414 ms 84304 KB Output is correct
27 Correct 393 ms 84304 KB Output is correct
28 Correct 43 ms 16976 KB Output is correct
29 Correct 196 ms 19588 KB Output is correct
30 Correct 435 ms 19696 KB Output is correct
31 Correct 210 ms 19540 KB Output is correct
32 Correct 138 ms 19784 KB Output is correct
33 Correct 403 ms 19792 KB Output is correct
34 Correct 42 ms 16976 KB Output is correct
35 Correct 1326 ms 84424 KB Output is correct
36 Correct 744 ms 83836 KB Output is correct
37 Correct 1066 ms 84020 KB Output is correct
38 Correct 32 ms 16988 KB Output is correct
39 Correct 472 ms 88480 KB Output is correct
40 Correct 1323 ms 88640 KB Output is correct
41 Correct 586 ms 87580 KB Output is correct
42 Correct 553 ms 87700 KB Output is correct
43 Correct 40 ms 16984 KB Output is correct
44 Correct 1148 ms 84348 KB Output is correct
45 Correct 491 ms 84252 KB Output is correct
46 Correct 560 ms 84584 KB Output is correct
47 Correct 506 ms 84712 KB Output is correct
48 Correct 2655 ms 86364 KB Output is correct
49 Execution timed out 3561 ms 87060 KB Time limit exceeded
50 Halted 0 ms 0 KB -