oj.uz

Submission #910140

# Submission time Handle Problem Language Result Execution time Memory
910140 2024-01-18T00:07:43 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 90224 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 = 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) {
// 			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 28 ms 16308 KB Output is correct
2 Correct 33 ms 18776 KB Output is correct
3 Correct 38 ms 19024 KB Output is correct
4 Correct 35 ms 19028 KB Output is correct
5 Correct 31 ms 19028 KB Output is correct
6 Correct 39 ms 19024 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16308 KB Output is correct
2 Correct 33 ms 18776 KB Output is correct
3 Correct 38 ms 19024 KB Output is correct
4 Correct 35 ms 19028 KB Output is correct
5 Correct 31 ms 19028 KB Output is correct
6 Correct 39 ms 19024 KB Output is correct
7 Correct 40 ms 16324 KB Output is correct
8 Correct 175 ms 18768 KB Output is correct
9 Correct 372 ms 18972 KB Output is correct
10 Correct 198 ms 18744 KB Output is correct
11 Correct 110 ms 19024 KB Output is correct
12 Correct 311 ms 19028 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16292 KB Output is correct
2 Correct 350 ms 82432 KB Output is correct
3 Correct 363 ms 82448 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16292 KB Output is correct
2 Correct 350 ms 82432 KB Output is correct
3 Correct 363 ms 82448 KB Output is correct
4 Correct 39 ms 16208 KB Output is correct
5 Correct 2354 ms 82492 KB Output is correct
6 Correct 1412 ms 82688 KB Output is correct
7 Correct 1740 ms 82916 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16220 KB Output is correct
2 Correct 332 ms 86284 KB Output is correct
3 Correct 336 ms 86368 KB Output is correct
4 Correct 403 ms 86096 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16220 KB Output is correct
2 Correct 332 ms 86284 KB Output is correct
3 Correct 336 ms 86368 KB Output is correct
4 Correct 403 ms 86096 KB Output is correct
5 Correct 28 ms 16296 KB Output is correct
6 Correct 471 ms 86136 KB Output is correct
7 Correct 1608 ms 90224 KB Output is correct
8 Correct 652 ms 86032 KB Output is correct
9 Correct 644 ms 86168 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16336 KB Output is correct
2 Correct 339 ms 82360 KB Output is correct
3 Correct 353 ms 82512 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16336 KB Output is correct
2 Correct 339 ms 82360 KB Output is correct
3 Correct 353 ms 82512 KB Output is correct
4 Correct 39 ms 16200 KB Output is correct
5 Correct 1292 ms 82576 KB Output is correct
6 Correct 562 ms 82756 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16220 KB Output is correct
2 Correct 372 ms 86268 KB Output is correct
3 Correct 411 ms 86284 KB Output is correct
4 Correct 414 ms 86196 KB Output is correct
5 Correct 27 ms 16220 KB Output is correct
6 Correct 356 ms 82516 KB Output is correct
7 Correct 393 ms 82516 KB Output is correct
8 Correct 386 ms 83040 KB Output is correct
9 Correct 502 ms 82996 KB Output is correct
10 Correct 676 ms 84624 KB Output is correct
11 Correct 639 ms 84152 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16220 KB Output is correct
2 Correct 372 ms 86268 KB Output is correct
3 Correct 411 ms 86284 KB Output is correct
4 Correct 414 ms 86196 KB Output is correct
5 Correct 27 ms 16220 KB Output is correct
6 Correct 356 ms 82516 KB Output is correct
7 Correct 393 ms 82516 KB Output is correct
8 Correct 386 ms 83040 KB Output is correct
9 Correct 502 ms 82996 KB Output is correct
10 Correct 676 ms 84624 KB Output is correct
11 Correct 639 ms 84152 KB Output is correct
12 Correct 40 ms 16380 KB Output is correct
13 Correct 672 ms 86248 KB Output is correct
14 Correct 1821 ms 90084 KB Output is correct
15 Correct 629 ms 86108 KB Output is correct
16 Correct 702 ms 86308 KB Output is correct
17 Correct 56 ms 16212 KB Output is correct
18 Correct 1331 ms 82548 KB Output is correct
19 Correct 627 ms 82512 KB Output is correct
20 Correct 705 ms 82920 KB Output is correct
21 Correct 750 ms 82928 KB Output is correct
22 Correct 3262 ms 85812 KB Output is correct
23 Execution timed out 3538 ms 86352 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16344 KB Output is correct
2 Correct 39 ms 18872 KB Output is correct
3 Correct 42 ms 18924 KB Output is correct
4 Correct 36 ms 18904 KB Output is correct
5 Correct 34 ms 19024 KB Output is correct
6 Correct 40 ms 19032 KB Output is correct
7 Correct 30 ms 16220 KB Output is correct
8 Correct 377 ms 82432 KB Output is correct
9 Correct 427 ms 82480 KB Output is correct
10 Correct 41 ms 16164 KB Output is correct
11 Correct 402 ms 86352 KB Output is correct
12 Correct 364 ms 86196 KB Output is correct
13 Correct 440 ms 86308 KB Output is correct
14 Correct 25 ms 16220 KB Output is correct
15 Correct 364 ms 82332 KB Output is correct
16 Correct 486 ms 82512 KB Output is correct
17 Correct 408 ms 82964 KB Output is correct
18 Correct 425 ms 83048 KB Output is correct
19 Correct 642 ms 84668 KB Output is correct
20 Correct 686 ms 84236 KB Output is correct
21 Correct 393 ms 82752 KB Output is correct
22 Correct 535 ms 82608 KB Output is correct
23 Correct 458 ms 83204 KB Output is correct
24 Correct 417 ms 83284 KB Output is correct
25 Correct 521 ms 83208 KB Output is correct
26 Correct 548 ms 82116 KB Output is correct
27 Correct 491 ms 82196 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16344 KB Output is correct
2 Correct 39 ms 18872 KB Output is correct
3 Correct 42 ms 18924 KB Output is correct
4 Correct 36 ms 18904 KB Output is correct
5 Correct 34 ms 19024 KB Output is correct
6 Correct 40 ms 19032 KB Output is correct
7 Correct 30 ms 16220 KB Output is correct
8 Correct 377 ms 82432 KB Output is correct
9 Correct 427 ms 82480 KB Output is correct
10 Correct 41 ms 16164 KB Output is correct
11 Correct 402 ms 86352 KB Output is correct
12 Correct 364 ms 86196 KB Output is correct
13 Correct 440 ms 86308 KB Output is correct
14 Correct 25 ms 16220 KB Output is correct
15 Correct 364 ms 82332 KB Output is correct
16 Correct 486 ms 82512 KB Output is correct
17 Correct 408 ms 82964 KB Output is correct
18 Correct 425 ms 83048 KB Output is correct
19 Correct 642 ms 84668 KB Output is correct
20 Correct 686 ms 84236 KB Output is correct
21 Correct 393 ms 82752 KB Output is correct
22 Correct 535 ms 82608 KB Output is correct
23 Correct 458 ms 83204 KB Output is correct
24 Correct 417 ms 83284 KB Output is correct
25 Correct 521 ms 83208 KB Output is correct
26 Correct 548 ms 82116 KB Output is correct
27 Correct 491 ms 82196 KB Output is correct
28 Correct 40 ms 16168 KB Output is correct
29 Correct 207 ms 18872 KB Output is correct
30 Correct 388 ms 19124 KB Output is correct
31 Correct 217 ms 18940 KB Output is correct
32 Correct 113 ms 18868 KB Output is correct
33 Correct 326 ms 18900 KB Output is correct
34 Correct 40 ms 16212 KB Output is correct
35 Execution timed out 3558 ms 82772 KB Time limit exceeded
36 Halted 0 ms 0 KB -