oj.uz

Submission #910177

# Submission time Handle Problem Language Result Execution time Memory
910177 2024-01-18T01:03:23 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 88996 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 = 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) {
			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
			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
			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 30 ms 16220 KB Output is correct
2 Correct 34 ms 18776 KB Output is correct
3 Correct 41 ms 19024 KB Output is correct
4 Correct 38 ms 19028 KB Output is correct
5 Correct 34 ms 19024 KB Output is correct
6 Correct 42 ms 19032 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16220 KB Output is correct
2 Correct 34 ms 18776 KB Output is correct
3 Correct 41 ms 19024 KB Output is correct
4 Correct 38 ms 19028 KB Output is correct
5 Correct 34 ms 19024 KB Output is correct
6 Correct 42 ms 19032 KB Output is correct
7 Correct 43 ms 16344 KB Output is correct
8 Correct 184 ms 18904 KB Output is correct
9 Correct 393 ms 19028 KB Output is correct
10 Correct 191 ms 18768 KB Output is correct
11 Correct 117 ms 19008 KB Output is correct
12 Correct 327 ms 19280 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 345 ms 82508 KB Output is correct
3 Correct 366 ms 82572 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 345 ms 82508 KB Output is correct
3 Correct 366 ms 82572 KB Output is correct
4 Correct 50 ms 16212 KB Output is correct
5 Correct 1484 ms 88252 KB Output is correct
6 Correct 1459 ms 88996 KB Output is correct
7 Correct 1838 ms 88464 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16220 KB Output is correct
2 Correct 314 ms 86356 KB Output is correct
3 Correct 311 ms 86352 KB Output is correct
4 Correct 403 ms 86356 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16220 KB Output is correct
2 Correct 314 ms 86356 KB Output is correct
3 Correct 311 ms 86352 KB Output is correct
4 Correct 403 ms 86356 KB Output is correct
5 Correct 30 ms 16364 KB Output is correct
6 Correct 461 ms 86356 KB Output is correct
7 Correct 1413 ms 86336 KB Output is correct
8 Correct 570 ms 86184 KB Output is correct
9 Correct 558 ms 86456 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16388 KB Output is correct
2 Correct 289 ms 82512 KB Output is correct
3 Correct 337 ms 82428 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16388 KB Output is correct
2 Correct 289 ms 82512 KB Output is correct
3 Correct 337 ms 82428 KB Output is correct
4 Correct 38 ms 16220 KB Output is correct
5 Correct 1128 ms 82424 KB Output is correct
6 Correct 481 ms 82456 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 323 ms 86560 KB Output is correct
3 Correct 337 ms 86348 KB Output is correct
4 Correct 356 ms 86540 KB Output is correct
5 Correct 28 ms 16212 KB Output is correct
6 Correct 290 ms 82512 KB Output is correct
7 Correct 350 ms 82504 KB Output is correct
8 Correct 329 ms 83028 KB Output is correct
9 Correct 382 ms 83356 KB Output is correct
10 Correct 560 ms 84628 KB Output is correct
11 Correct 547 ms 84108 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 323 ms 86560 KB Output is correct
3 Correct 337 ms 86348 KB Output is correct
4 Correct 356 ms 86540 KB Output is correct
5 Correct 28 ms 16212 KB Output is correct
6 Correct 290 ms 82512 KB Output is correct
7 Correct 350 ms 82504 KB Output is correct
8 Correct 329 ms 83028 KB Output is correct
9 Correct 382 ms 83356 KB Output is correct
10 Correct 560 ms 84628 KB Output is correct
11 Correct 547 ms 84108 KB Output is correct
12 Correct 33 ms 16212 KB Output is correct
13 Correct 434 ms 86448 KB Output is correct
14 Correct 1286 ms 86340 KB Output is correct
15 Correct 519 ms 86140 KB Output is correct
16 Correct 539 ms 86356 KB Output is correct
17 Correct 38 ms 16208 KB Output is correct
18 Correct 1090 ms 83056 KB Output is correct
19 Correct 483 ms 82492 KB Output is correct
20 Correct 573 ms 82816 KB Output is correct
21 Correct 521 ms 83028 KB Output is correct
22 Correct 2986 ms 84380 KB Output is correct
23 Execution timed out 3515 ms 85028 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 34 ms 19024 KB Output is correct
3 Correct 45 ms 18924 KB Output is correct
4 Correct 37 ms 19024 KB Output is correct
5 Correct 33 ms 19036 KB Output is correct
6 Correct 43 ms 18952 KB Output is correct
7 Correct 33 ms 16176 KB Output is correct
8 Correct 339 ms 82436 KB Output is correct
9 Correct 337 ms 82592 KB Output is correct
10 Correct 26 ms 16208 KB Output is correct
11 Correct 315 ms 86248 KB Output is correct
12 Correct 314 ms 86184 KB Output is correct
13 Correct 370 ms 86448 KB Output is correct
14 Correct 27 ms 16220 KB Output is correct
15 Correct 289 ms 82516 KB Output is correct
16 Correct 350 ms 82460 KB Output is correct
17 Correct 360 ms 82952 KB Output is correct
18 Correct 414 ms 83088 KB Output is correct
19 Correct 597 ms 84820 KB Output is correct
20 Correct 589 ms 84164 KB Output is correct
21 Correct 380 ms 82364 KB Output is correct
22 Correct 368 ms 83064 KB Output is correct
23 Correct 370 ms 83168 KB Output is correct
24 Correct 355 ms 83456 KB Output is correct
25 Correct 367 ms 83128 KB Output is correct
26 Correct 428 ms 82000 KB Output is correct
27 Correct 444 ms 81956 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 34 ms 19024 KB Output is correct
3 Correct 45 ms 18924 KB Output is correct
4 Correct 37 ms 19024 KB Output is correct
5 Correct 33 ms 19036 KB Output is correct
6 Correct 43 ms 18952 KB Output is correct
7 Correct 33 ms 16176 KB Output is correct
8 Correct 339 ms 82436 KB Output is correct
9 Correct 337 ms 82592 KB Output is correct
10 Correct 26 ms 16208 KB Output is correct
11 Correct 315 ms 86248 KB Output is correct
12 Correct 314 ms 86184 KB Output is correct
13 Correct 370 ms 86448 KB Output is correct
14 Correct 27 ms 16220 KB Output is correct
15 Correct 289 ms 82516 KB Output is correct
16 Correct 350 ms 82460 KB Output is correct
17 Correct 360 ms 82952 KB Output is correct
18 Correct 414 ms 83088 KB Output is correct
19 Correct 597 ms 84820 KB Output is correct
20 Correct 589 ms 84164 KB Output is correct
21 Correct 380 ms 82364 KB Output is correct
22 Correct 368 ms 83064 KB Output is correct
23 Correct 370 ms 83168 KB Output is correct
24 Correct 355 ms 83456 KB Output is correct
25 Correct 367 ms 83128 KB Output is correct
26 Correct 428 ms 82000 KB Output is correct
27 Correct 444 ms 81956 KB Output is correct
28 Correct 45 ms 16220 KB Output is correct
29 Correct 211 ms 19052 KB Output is correct
30 Correct 405 ms 19280 KB Output is correct
31 Correct 189 ms 18768 KB Output is correct
32 Correct 158 ms 19028 KB Output is correct
33 Correct 364 ms 19204 KB Output is correct
34 Correct 42 ms 16216 KB Output is correct
35 Correct 1117 ms 88028 KB Output is correct
36 Correct 1745 ms 88392 KB Output is correct
37 Correct 2161 ms 88580 KB Output is correct
38 Correct 30 ms 16176 KB Output is correct
39 Correct 504 ms 86136 KB Output is correct
40 Correct 1422 ms 86448 KB Output is correct
41 Correct 574 ms 86100 KB Output is correct
42 Correct 546 ms 86280 KB Output is correct
43 Correct 39 ms 16216 KB Output is correct
44 Correct 1264 ms 82572 KB Output is correct
45 Correct 502 ms 82552 KB Output is correct
46 Correct 560 ms 82980 KB Output is correct
47 Correct 505 ms 82772 KB Output is correct
48 Correct 2646 ms 84176 KB Output is correct
49 Execution timed out 3559 ms 84840 KB Time limit exceeded
50 Halted 0 ms 0 KB -