oj.uz

Submission #910159

# Submission time Handle Problem Language Result Execution time Memory
910159 2024-01-18T00:44:13 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 89596 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 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';
#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 33 ms 18972 KB Output is correct
3 Correct 40 ms 19028 KB Output is correct
4 Correct 36 ms 19024 KB Output is correct
5 Correct 32 ms 19024 KB Output is correct
6 Correct 42 ms 18952 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 33 ms 18972 KB Output is correct
3 Correct 40 ms 19028 KB Output is correct
4 Correct 36 ms 19024 KB Output is correct
5 Correct 32 ms 19024 KB Output is correct
6 Correct 42 ms 18952 KB Output is correct
7 Correct 47 ms 16364 KB Output is correct
8 Correct 189 ms 18940 KB Output is correct
9 Correct 397 ms 19444 KB Output is correct
10 Correct 193 ms 18768 KB Output is correct
11 Correct 108 ms 19028 KB Output is correct
12 Correct 324 ms 19064 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 338 ms 82432 KB Output is correct
3 Correct 338 ms 84228 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 338 ms 82432 KB Output is correct
3 Correct 338 ms 84228 KB Output is correct
4 Correct 41 ms 16920 KB Output is correct
5 Correct 1194 ms 89472 KB Output is correct
6 Correct 1417 ms 89596 KB Output is correct
7 Correct 1459 ms 89584 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 350 ms 86352 KB Output is correct
3 Correct 331 ms 88324 KB Output is correct
4 Correct 350 ms 88148 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 350 ms 86352 KB Output is correct
3 Correct 331 ms 88324 KB Output is correct
4 Correct 350 ms 88148 KB Output is correct
5 Correct 29 ms 16984 KB Output is correct
6 Correct 432 ms 88056 KB Output is correct
7 Correct 1257 ms 88324 KB Output is correct
8 Correct 536 ms 87476 KB Output is correct
9 Correct 521 ms 87516 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16216 KB Output is correct
2 Correct 309 ms 82484 KB Output is correct
3 Correct 338 ms 84560 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16216 KB Output is correct
2 Correct 309 ms 82484 KB Output is correct
3 Correct 338 ms 84560 KB Output is correct
4 Correct 40 ms 16980 KB Output is correct
5 Correct 1106 ms 84428 KB Output is correct
6 Correct 453 ms 84304 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16212 KB Output is correct
2 Correct 329 ms 86380 KB Output is correct
3 Correct 322 ms 88344 KB Output is correct
4 Correct 375 ms 88244 KB Output is correct
5 Correct 29 ms 16980 KB Output is correct
6 Correct 304 ms 84644 KB Output is correct
7 Correct 337 ms 84436 KB Output is correct
8 Correct 325 ms 84952 KB Output is correct
9 Correct 355 ms 84952 KB Output is correct
10 Correct 560 ms 86868 KB Output is correct
11 Correct 579 ms 86176 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16212 KB Output is correct
2 Correct 329 ms 86380 KB Output is correct
3 Correct 322 ms 88344 KB Output is correct
4 Correct 375 ms 88244 KB Output is correct
5 Correct 29 ms 16980 KB Output is correct
6 Correct 304 ms 84644 KB Output is correct
7 Correct 337 ms 84436 KB Output is correct
8 Correct 325 ms 84952 KB Output is correct
9 Correct 355 ms 84952 KB Output is correct
10 Correct 560 ms 86868 KB Output is correct
11 Correct 579 ms 86176 KB Output is correct
12 Correct 31 ms 16976 KB Output is correct
13 Correct 457 ms 88304 KB Output is correct
14 Correct 1290 ms 88148 KB Output is correct
15 Correct 526 ms 87940 KB Output is correct
16 Correct 531 ms 87892 KB Output is correct
17 Correct 39 ms 16976 KB Output is correct
18 Correct 1097 ms 84620 KB Output is correct
19 Correct 459 ms 84360 KB Output is correct
20 Correct 538 ms 85240 KB Output is correct
21 Correct 487 ms 84752 KB Output is correct
22 Correct 2417 ms 85912 KB Output is correct
23 Execution timed out 3584 ms 85180 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 16212 KB Output is correct
2 Correct 37 ms 18776 KB Output is correct
3 Correct 47 ms 19036 KB Output is correct
4 Correct 37 ms 19036 KB Output is correct
5 Correct 33 ms 19024 KB Output is correct
6 Correct 42 ms 18900 KB Output is correct
7 Correct 32 ms 16216 KB Output is correct
8 Correct 345 ms 82452 KB Output is correct
9 Correct 320 ms 82536 KB Output is correct
10 Correct 28 ms 16216 KB Output is correct
11 Correct 324 ms 86636 KB Output is correct
12 Correct 300 ms 86352 KB Output is correct
13 Correct 362 ms 86564 KB Output is correct
14 Correct 29 ms 16208 KB Output is correct
15 Correct 290 ms 82512 KB Output is correct
16 Correct 340 ms 82416 KB Output is correct
17 Correct 330 ms 82812 KB Output is correct
18 Correct 362 ms 83048 KB Output is correct
19 Correct 555 ms 84708 KB Output is correct
20 Correct 550 ms 84268 KB Output is correct
21 Correct 342 ms 82396 KB Output is correct
22 Correct 339 ms 82720 KB Output is correct
23 Correct 338 ms 83172 KB Output is correct
24 Correct 344 ms 83216 KB Output is correct
25 Correct 356 ms 83120 KB Output is correct
26 Correct 411 ms 82004 KB Output is correct
27 Correct 384 ms 81948 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16212 KB Output is correct
2 Correct 37 ms 18776 KB Output is correct
3 Correct 47 ms 19036 KB Output is correct
4 Correct 37 ms 19036 KB Output is correct
5 Correct 33 ms 19024 KB Output is correct
6 Correct 42 ms 18900 KB Output is correct
7 Correct 32 ms 16216 KB Output is correct
8 Correct 345 ms 82452 KB Output is correct
9 Correct 320 ms 82536 KB Output is correct
10 Correct 28 ms 16216 KB Output is correct
11 Correct 324 ms 86636 KB Output is correct
12 Correct 300 ms 86352 KB Output is correct
13 Correct 362 ms 86564 KB Output is correct
14 Correct 29 ms 16208 KB Output is correct
15 Correct 290 ms 82512 KB Output is correct
16 Correct 340 ms 82416 KB Output is correct
17 Correct 330 ms 82812 KB Output is correct
18 Correct 362 ms 83048 KB Output is correct
19 Correct 555 ms 84708 KB Output is correct
20 Correct 550 ms 84268 KB Output is correct
21 Correct 342 ms 82396 KB Output is correct
22 Correct 339 ms 82720 KB Output is correct
23 Correct 338 ms 83172 KB Output is correct
24 Correct 344 ms 83216 KB Output is correct
25 Correct 356 ms 83120 KB Output is correct
26 Correct 411 ms 82004 KB Output is correct
27 Correct 384 ms 81948 KB Output is correct
28 Correct 42 ms 16216 KB Output is correct
29 Correct 191 ms 19148 KB Output is correct
30 Correct 391 ms 19024 KB Output is correct
31 Correct 191 ms 18952 KB Output is correct
32 Correct 109 ms 19020 KB Output is correct
33 Correct 313 ms 19284 KB Output is correct
34 Correct 41 ms 16360 KB Output is correct
35 Correct 1120 ms 88160 KB Output is correct
36 Correct 1493 ms 88276 KB Output is correct
37 Correct 1651 ms 88320 KB Output is correct
38 Correct 29 ms 16216 KB Output is correct
39 Correct 436 ms 86168 KB Output is correct
40 Correct 1256 ms 86352 KB Output is correct
41 Correct 533 ms 86052 KB Output is correct
42 Correct 542 ms 86352 KB Output is correct
43 Correct 37 ms 16208 KB Output is correct
44 Correct 1094 ms 82776 KB Output is correct
45 Correct 473 ms 82304 KB Output is correct
46 Correct 530 ms 83284 KB Output is correct
47 Correct 488 ms 82968 KB Output is correct
48 Correct 2409 ms 84488 KB Output is correct
49 Execution timed out 3542 ms 84756 KB Time limit exceeded
50 Halted 0 ms 0 KB -