oj.uz

Submission #910149

# Submission time Handle Problem Language Result Execution time Memory
910149 2024-01-18T00:24:44 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 87016 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 = 400;
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: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 28 ms 16220 KB Output is correct
2 Correct 32 ms 18880 KB Output is correct
3 Correct 39 ms 18968 KB Output is correct
4 Correct 35 ms 19024 KB Output is correct
5 Correct 31 ms 19144 KB Output is correct
6 Correct 40 ms 19028 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16220 KB Output is correct
2 Correct 32 ms 18880 KB Output is correct
3 Correct 39 ms 18968 KB Output is correct
4 Correct 35 ms 19024 KB Output is correct
5 Correct 31 ms 19144 KB Output is correct
6 Correct 40 ms 19028 KB Output is correct
7 Correct 40 ms 16216 KB Output is correct
8 Correct 196 ms 18920 KB Output is correct
9 Correct 445 ms 19148 KB Output is correct
10 Correct 214 ms 19220 KB Output is correct
11 Correct 255 ms 19036 KB Output is correct
12 Correct 600 ms 19024 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16220 KB Output is correct
2 Correct 348 ms 82728 KB Output is correct
3 Correct 327 ms 82588 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16220 KB Output is correct
2 Correct 348 ms 82728 KB Output is correct
3 Correct 327 ms 82588 KB Output is correct
4 Correct 39 ms 16208 KB Output is correct
5 Correct 1288 ms 82688 KB Output is correct
6 Correct 765 ms 83076 KB Output is correct
7 Correct 1053 ms 82688 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16212 KB Output is correct
2 Correct 310 ms 86152 KB Output is correct
3 Correct 307 ms 86364 KB Output is correct
4 Correct 361 ms 86152 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16212 KB Output is correct
2 Correct 310 ms 86152 KB Output is correct
3 Correct 307 ms 86364 KB Output is correct
4 Correct 361 ms 86152 KB Output is correct
5 Correct 28 ms 16220 KB Output is correct
6 Correct 459 ms 86096 KB Output is correct
7 Correct 1340 ms 87016 KB Output is correct
8 Correct 632 ms 86100 KB Output is correct
9 Correct 586 ms 86052 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16208 KB Output is correct
2 Correct 272 ms 82392 KB Output is correct
3 Correct 346 ms 82544 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16208 KB Output is correct
2 Correct 272 ms 82392 KB Output is correct
3 Correct 346 ms 82544 KB Output is correct
4 Correct 36 ms 16220 KB Output is correct
5 Correct 1247 ms 82904 KB Output is correct
6 Correct 454 ms 82772 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16220 KB Output is correct
2 Correct 308 ms 86300 KB Output is correct
3 Correct 303 ms 86532 KB Output is correct
4 Correct 366 ms 86352 KB Output is correct
5 Correct 32 ms 16216 KB Output is correct
6 Correct 298 ms 82516 KB Output is correct
7 Correct 315 ms 82468 KB Output is correct
8 Correct 321 ms 83036 KB Output is correct
9 Correct 368 ms 83280 KB Output is correct
10 Correct 532 ms 84680 KB Output is correct
11 Correct 542 ms 84432 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16220 KB Output is correct
2 Correct 308 ms 86300 KB Output is correct
3 Correct 303 ms 86532 KB Output is correct
4 Correct 366 ms 86352 KB Output is correct
5 Correct 32 ms 16216 KB Output is correct
6 Correct 298 ms 82516 KB Output is correct
7 Correct 315 ms 82468 KB Output is correct
8 Correct 321 ms 83036 KB Output is correct
9 Correct 368 ms 83280 KB Output is correct
10 Correct 532 ms 84680 KB Output is correct
11 Correct 542 ms 84432 KB Output is correct
12 Correct 27 ms 16220 KB Output is correct
13 Correct 463 ms 86272 KB Output is correct
14 Correct 1335 ms 86996 KB Output is correct
15 Correct 578 ms 86100 KB Output is correct
16 Correct 568 ms 86144 KB Output is correct
17 Correct 35 ms 16356 KB Output is correct
18 Correct 1278 ms 82608 KB Output is correct
19 Correct 450 ms 82644 KB Output is correct
20 Correct 598 ms 82980 KB Output is correct
21 Correct 499 ms 82972 KB Output is correct
22 Correct 2551 ms 84524 KB Output is correct
23 Execution timed out 3536 ms 85072 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 16216 KB Output is correct
2 Correct 34 ms 18768 KB Output is correct
3 Correct 48 ms 19024 KB Output is correct
4 Correct 35 ms 19036 KB Output is correct
5 Correct 36 ms 19024 KB Output is correct
6 Correct 40 ms 19028 KB Output is correct
7 Correct 31 ms 16208 KB Output is correct
8 Correct 328 ms 82556 KB Output is correct
9 Correct 342 ms 82556 KB Output is correct
10 Correct 24 ms 16208 KB Output is correct
11 Correct 326 ms 86784 KB Output is correct
12 Correct 300 ms 86356 KB Output is correct
13 Correct 363 ms 86592 KB Output is correct
14 Correct 25 ms 16220 KB Output is correct
15 Correct 273 ms 82392 KB Output is correct
16 Correct 339 ms 82512 KB Output is correct
17 Correct 326 ms 82908 KB Output is correct
18 Correct 357 ms 83204 KB Output is correct
19 Correct 531 ms 84564 KB Output is correct
20 Correct 532 ms 84192 KB Output is correct
21 Correct 340 ms 82552 KB Output is correct
22 Correct 347 ms 82520 KB Output is correct
23 Correct 345 ms 83196 KB Output is correct
24 Correct 348 ms 83280 KB Output is correct
25 Correct 392 ms 83216 KB Output is correct
26 Correct 400 ms 81952 KB Output is correct
27 Correct 365 ms 81952 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 16216 KB Output is correct
2 Correct 34 ms 18768 KB Output is correct
3 Correct 48 ms 19024 KB Output is correct
4 Correct 35 ms 19036 KB Output is correct
5 Correct 36 ms 19024 KB Output is correct
6 Correct 40 ms 19028 KB Output is correct
7 Correct 31 ms 16208 KB Output is correct
8 Correct 328 ms 82556 KB Output is correct
9 Correct 342 ms 82556 KB Output is correct
10 Correct 24 ms 16208 KB Output is correct
11 Correct 326 ms 86784 KB Output is correct
12 Correct 300 ms 86356 KB Output is correct
13 Correct 363 ms 86592 KB Output is correct
14 Correct 25 ms 16220 KB Output is correct
15 Correct 273 ms 82392 KB Output is correct
16 Correct 339 ms 82512 KB Output is correct
17 Correct 326 ms 82908 KB Output is correct
18 Correct 357 ms 83204 KB Output is correct
19 Correct 531 ms 84564 KB Output is correct
20 Correct 532 ms 84192 KB Output is correct
21 Correct 340 ms 82552 KB Output is correct
22 Correct 347 ms 82520 KB Output is correct
23 Correct 345 ms 83196 KB Output is correct
24 Correct 348 ms 83280 KB Output is correct
25 Correct 392 ms 83216 KB Output is correct
26 Correct 400 ms 81952 KB Output is correct
27 Correct 365 ms 81952 KB Output is correct
28 Correct 41 ms 16216 KB Output is correct
29 Correct 197 ms 18832 KB Output is correct
30 Correct 458 ms 19184 KB Output is correct
31 Correct 212 ms 18948 KB Output is correct
32 Correct 264 ms 19176 KB Output is correct
33 Correct 591 ms 18908 KB Output is correct
34 Correct 39 ms 16232 KB Output is correct
35 Correct 1309 ms 82696 KB Output is correct
36 Correct 717 ms 82688 KB Output is correct
37 Correct 1028 ms 82704 KB Output is correct
38 Correct 28 ms 16220 KB Output is correct
39 Correct 463 ms 86104 KB Output is correct
40 Correct 1336 ms 86868 KB Output is correct
41 Correct 567 ms 86220 KB Output is correct
42 Correct 580 ms 86100 KB Output is correct
43 Correct 36 ms 16216 KB Output is correct
44 Correct 1230 ms 82580 KB Output is correct
45 Correct 457 ms 82500 KB Output is correct
46 Correct 592 ms 82940 KB Output is correct
47 Correct 492 ms 82768 KB Output is correct
48 Correct 2801 ms 84444 KB Output is correct
49 Execution timed out 3604 ms 85480 KB Time limit exceeded
50 Halted 0 ms 0 KB -