oj.uz

Submission #910161

# Submission time Handle Problem Language Result Execution time Memory
910161 2024-01-18T00:46:54 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 88492 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,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 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;
	}
// 	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 = 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)) {
					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\n";
#endif
	return 0;
}

Compilation message

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 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 35 ms 19064 KB Output is correct
5 Correct 33 ms 19032 KB Output is correct
6 Correct 42 ms 18864 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 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 35 ms 19064 KB Output is correct
5 Correct 33 ms 19032 KB Output is correct
6 Correct 42 ms 18864 KB Output is correct
7 Correct 43 ms 16384 KB Output is correct
8 Correct 184 ms 18692 KB Output is correct
9 Correct 397 ms 19024 KB Output is correct
10 Correct 196 ms 18856 KB Output is correct
11 Correct 110 ms 18924 KB Output is correct
12 Correct 320 ms 19248 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16208 KB Output is correct
2 Correct 348 ms 82692 KB Output is correct
3 Correct 342 ms 82636 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16208 KB Output is correct
2 Correct 348 ms 82692 KB Output is correct
3 Correct 342 ms 82636 KB Output is correct
4 Correct 41 ms 16220 KB Output is correct
5 Correct 1121 ms 88376 KB Output is correct
6 Correct 1127 ms 88332 KB Output is correct
7 Correct 1403 ms 88448 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16288 KB Output is correct
2 Correct 309 ms 86260 KB Output is correct
3 Correct 308 ms 86612 KB Output is correct
4 Correct 357 ms 86096 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16288 KB Output is correct
2 Correct 309 ms 86260 KB Output is correct
3 Correct 308 ms 86612 KB Output is correct
4 Correct 357 ms 86096 KB Output is correct
5 Correct 29 ms 16208 KB Output is correct
6 Correct 469 ms 86236 KB Output is correct
7 Correct 1285 ms 86364 KB Output is correct
8 Correct 548 ms 86156 KB Output is correct
9 Correct 534 ms 86568 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16348 KB Output is correct
2 Correct 300 ms 82528 KB Output is correct
3 Correct 333 ms 82396 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16348 KB Output is correct
2 Correct 300 ms 82528 KB Output is correct
3 Correct 333 ms 82396 KB Output is correct
4 Correct 38 ms 16220 KB Output is correct
5 Correct 1168 ms 82352 KB Output is correct
6 Correct 475 ms 82512 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 346 ms 86160 KB Output is correct
3 Correct 342 ms 86308 KB Output is correct
4 Correct 369 ms 86256 KB Output is correct
5 Correct 28 ms 16208 KB Output is correct
6 Correct 287 ms 82436 KB Output is correct
7 Correct 401 ms 82492 KB Output is correct
8 Correct 329 ms 82872 KB Output is correct
9 Correct 374 ms 83032 KB Output is correct
10 Correct 593 ms 84500 KB Output is correct
11 Correct 552 ms 84268 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 346 ms 86160 KB Output is correct
3 Correct 342 ms 86308 KB Output is correct
4 Correct 369 ms 86256 KB Output is correct
5 Correct 28 ms 16208 KB Output is correct
6 Correct 287 ms 82436 KB Output is correct
7 Correct 401 ms 82492 KB Output is correct
8 Correct 329 ms 82872 KB Output is correct
9 Correct 374 ms 83032 KB Output is correct
10 Correct 593 ms 84500 KB Output is correct
11 Correct 552 ms 84268 KB Output is correct
12 Correct 29 ms 16160 KB Output is correct
13 Correct 427 ms 86080 KB Output is correct
14 Correct 1247 ms 86428 KB Output is correct
15 Correct 518 ms 86136 KB Output is correct
16 Correct 540 ms 86364 KB Output is correct
17 Correct 38 ms 16356 KB Output is correct
18 Correct 1097 ms 82568 KB Output is correct
19 Correct 474 ms 82404 KB Output is correct
20 Correct 558 ms 83184 KB Output is correct
21 Correct 485 ms 82772 KB Output is correct
22 Correct 2464 ms 84088 KB Output is correct
23 Execution timed out 3513 ms 84876 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 16376 KB Output is correct
2 Correct 41 ms 18860 KB Output is correct
3 Correct 41 ms 19032 KB Output is correct
4 Correct 37 ms 19024 KB Output is correct
5 Correct 40 ms 19024 KB Output is correct
6 Correct 40 ms 18904 KB Output is correct
7 Correct 34 ms 16292 KB Output is correct
8 Correct 335 ms 82604 KB Output is correct
9 Correct 362 ms 82432 KB Output is correct
10 Correct 31 ms 16216 KB Output is correct
11 Correct 318 ms 86288 KB Output is correct
12 Correct 319 ms 86384 KB Output is correct
13 Correct 435 ms 86096 KB Output is correct
14 Correct 41 ms 16232 KB Output is correct
15 Correct 323 ms 82768 KB Output is correct
16 Correct 398 ms 82576 KB Output is correct
17 Correct 380 ms 82996 KB Output is correct
18 Correct 444 ms 82980 KB Output is correct
19 Correct 624 ms 84688 KB Output is correct
20 Correct 623 ms 84252 KB Output is correct
21 Correct 336 ms 82548 KB Output is correct
22 Correct 386 ms 82504 KB Output is correct
23 Correct 413 ms 83260 KB Output is correct
24 Correct 384 ms 83140 KB Output is correct
25 Correct 469 ms 83248 KB Output is correct
26 Correct 468 ms 81952 KB Output is correct
27 Correct 427 ms 82148 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16376 KB Output is correct
2 Correct 41 ms 18860 KB Output is correct
3 Correct 41 ms 19032 KB Output is correct
4 Correct 37 ms 19024 KB Output is correct
5 Correct 40 ms 19024 KB Output is correct
6 Correct 40 ms 18904 KB Output is correct
7 Correct 34 ms 16292 KB Output is correct
8 Correct 335 ms 82604 KB Output is correct
9 Correct 362 ms 82432 KB Output is correct
10 Correct 31 ms 16216 KB Output is correct
11 Correct 318 ms 86288 KB Output is correct
12 Correct 319 ms 86384 KB Output is correct
13 Correct 435 ms 86096 KB Output is correct
14 Correct 41 ms 16232 KB Output is correct
15 Correct 323 ms 82768 KB Output is correct
16 Correct 398 ms 82576 KB Output is correct
17 Correct 380 ms 82996 KB Output is correct
18 Correct 444 ms 82980 KB Output is correct
19 Correct 624 ms 84688 KB Output is correct
20 Correct 623 ms 84252 KB Output is correct
21 Correct 336 ms 82548 KB Output is correct
22 Correct 386 ms 82504 KB Output is correct
23 Correct 413 ms 83260 KB Output is correct
24 Correct 384 ms 83140 KB Output is correct
25 Correct 469 ms 83248 KB Output is correct
26 Correct 468 ms 81952 KB Output is correct
27 Correct 427 ms 82148 KB Output is correct
28 Correct 63 ms 16240 KB Output is correct
29 Correct 208 ms 18800 KB Output is correct
30 Correct 401 ms 18960 KB Output is correct
31 Correct 250 ms 18768 KB Output is correct
32 Correct 120 ms 18912 KB Output is correct
33 Correct 327 ms 19180 KB Output is correct
34 Correct 50 ms 16368 KB Output is correct
35 Correct 2884 ms 88168 KB Output is correct
36 Correct 1665 ms 88464 KB Output is correct
37 Correct 1746 ms 88492 KB Output is correct
38 Correct 30 ms 16216 KB Output is correct
39 Correct 631 ms 86220 KB Output is correct
40 Correct 1529 ms 86512 KB Output is correct
41 Correct 571 ms 86528 KB Output is correct
42 Correct 673 ms 86428 KB Output is correct
43 Correct 41 ms 16388 KB Output is correct
44 Correct 1289 ms 82560 KB Output is correct
45 Correct 557 ms 82420 KB Output is correct
46 Correct 643 ms 82948 KB Output is correct
47 Correct 633 ms 83244 KB Output is correct
48 Correct 2946 ms 84108 KB Output is correct
49 Execution timed out 3550 ms 85020 KB Time limit exceeded
50 Halted 0 ms 0 KB -