oj.uz

Submission #910137

# Submission time Handle Problem Language Result Execution time Memory
910137 2024-01-17T23:59:19 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 90664 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[2][18][N];
int st[N], en[N], curt;
void dfs(int i, int par, int part) {
	bl[0][0][i] = {par, part, part};
	bl[1][0][i] = {par, part, part};
	for (int j = 1; j < 18; j++) {
		bl[0][j][i] = bl[0][j - 1][i];
		auto [lst, lstt, mx] = bl[0][j][i];
		if (lstt <= bl[0][0][lst][1]) {
			bl[0][j][i] = bl[0][j - 1][lst];
			bl[0][j][i][2] = max(bl[0][j][i][2], mx);
		}
	}
	for (int j = 1; j < 18; j++) {
		bl[1][j][i] = bl[1][j - 1][i];
		auto [lst, lstt, mx] = bl[1][j][i];
		if (lstt >= bl[1][0][lst][1]) {
			bl[1][j][i] = bl[1][j - 1][lst];
			bl[1][j][i][2] = max(bl[1][j][i][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[t][17][a][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[t][j][a][0], b) && !isanc(bl[t][j][a][0], high)) {
			mx = max(mx, bl[t][j][a][2]);
			a = bl[t][j][a][0];
		}
	}
	return {max(mx, bl[t][0][a][2]), bl[t][0][a][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:86:7: warning: unused variable 'S' [-Wunused-variable]
   86 |  auto S = chrono::steady_clock::now().time_since_epoch().count();
      |       ^
servers.cpp:119:5: warning: unused variable 's' [-Wunused-variable]
  119 |  ll s = 0;
      |     ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65620 KB Output is correct
2 Correct 40 ms 66128 KB Output is correct
3 Correct 48 ms 66132 KB Output is correct
4 Correct 44 ms 66356 KB Output is correct
5 Correct 38 ms 66132 KB Output is correct
6 Correct 50 ms 66128 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65620 KB Output is correct
2 Correct 40 ms 66128 KB Output is correct
3 Correct 48 ms 66132 KB Output is correct
4 Correct 44 ms 66356 KB Output is correct
5 Correct 38 ms 66132 KB Output is correct
6 Correct 50 ms 66128 KB Output is correct
7 Correct 46 ms 65608 KB Output is correct
8 Correct 190 ms 66336 KB Output is correct
9 Correct 358 ms 66132 KB Output is correct
10 Correct 184 ms 66128 KB Output is correct
11 Correct 114 ms 66060 KB Output is correct
12 Correct 304 ms 66132 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 65504 KB Output is correct
2 Correct 489 ms 82428 KB Output is correct
3 Correct 517 ms 82532 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 65504 KB Output is correct
2 Correct 489 ms 82428 KB Output is correct
3 Correct 517 ms 82532 KB Output is correct
4 Correct 45 ms 65456 KB Output is correct
5 Correct 2643 ms 82688 KB Output is correct
6 Correct 1401 ms 82884 KB Output is correct
7 Correct 1715 ms 82772 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65616 KB Output is correct
2 Correct 377 ms 86352 KB Output is correct
3 Correct 374 ms 86376 KB Output is correct
4 Correct 369 ms 86192 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65616 KB Output is correct
2 Correct 377 ms 86352 KB Output is correct
3 Correct 374 ms 86376 KB Output is correct
4 Correct 369 ms 86192 KB Output is correct
5 Correct 35 ms 65628 KB Output is correct
6 Correct 505 ms 86324 KB Output is correct
7 Correct 1397 ms 90664 KB Output is correct
8 Correct 569 ms 86100 KB Output is correct
9 Correct 589 ms 86116 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65544 KB Output is correct
2 Correct 348 ms 82520 KB Output is correct
3 Correct 381 ms 82512 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65544 KB Output is correct
2 Correct 348 ms 82520 KB Output is correct
3 Correct 381 ms 82512 KB Output is correct
4 Correct 42 ms 65616 KB Output is correct
5 Correct 1114 ms 82572 KB Output is correct
6 Correct 504 ms 82748 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65616 KB Output is correct
2 Correct 367 ms 86284 KB Output is correct
3 Correct 375 ms 86596 KB Output is correct
4 Correct 379 ms 86304 KB Output is correct
5 Correct 38 ms 65792 KB Output is correct
6 Correct 332 ms 82480 KB Output is correct
7 Correct 385 ms 82516 KB Output is correct
8 Correct 389 ms 83032 KB Output is correct
9 Correct 467 ms 83280 KB Output is correct
10 Correct 677 ms 84820 KB Output is correct
11 Correct 718 ms 84484 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65616 KB Output is correct
2 Correct 367 ms 86284 KB Output is correct
3 Correct 375 ms 86596 KB Output is correct
4 Correct 379 ms 86304 KB Output is correct
5 Correct 38 ms 65792 KB Output is correct
6 Correct 332 ms 82480 KB Output is correct
7 Correct 385 ms 82516 KB Output is correct
8 Correct 389 ms 83032 KB Output is correct
9 Correct 467 ms 83280 KB Output is correct
10 Correct 677 ms 84820 KB Output is correct
11 Correct 718 ms 84484 KB Output is correct
12 Correct 35 ms 65620 KB Output is correct
13 Correct 504 ms 86516 KB Output is correct
14 Correct 1366 ms 90372 KB Output is correct
15 Correct 601 ms 86436 KB Output is correct
16 Correct 582 ms 86052 KB Output is correct
17 Correct 41 ms 65364 KB Output is correct
18 Correct 1055 ms 83096 KB Output is correct
19 Correct 500 ms 82752 KB Output is correct
20 Correct 598 ms 82932 KB Output is correct
21 Correct 613 ms 82980 KB Output is correct
22 Correct 2840 ms 85584 KB Output is correct
23 Execution timed out 3565 ms 86424 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 65536 KB Output is correct
2 Correct 39 ms 66128 KB Output is correct
3 Correct 47 ms 66112 KB Output is correct
4 Correct 43 ms 66132 KB Output is correct
5 Correct 39 ms 66288 KB Output is correct
6 Correct 49 ms 66128 KB Output is correct
7 Correct 40 ms 65620 KB Output is correct
8 Correct 497 ms 82448 KB Output is correct
9 Correct 534 ms 82804 KB Output is correct
10 Correct 32 ms 65608 KB Output is correct
11 Correct 374 ms 86312 KB Output is correct
12 Correct 434 ms 86288 KB Output is correct
13 Correct 381 ms 86096 KB Output is correct
14 Correct 32 ms 65620 KB Output is correct
15 Correct 335 ms 82392 KB Output is correct
16 Correct 394 ms 82516 KB Output is correct
17 Correct 407 ms 82964 KB Output is correct
18 Correct 472 ms 83080 KB Output is correct
19 Correct 717 ms 84816 KB Output is correct
20 Correct 703 ms 84564 KB Output is correct
21 Correct 485 ms 82372 KB Output is correct
22 Correct 498 ms 82560 KB Output is correct
23 Correct 472 ms 83304 KB Output is correct
24 Correct 466 ms 83384 KB Output is correct
25 Correct 477 ms 83204 KB Output is correct
26 Correct 554 ms 81940 KB Output is correct
27 Correct 487 ms 82256 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 65536 KB Output is correct
2 Correct 39 ms 66128 KB Output is correct
3 Correct 47 ms 66112 KB Output is correct
4 Correct 43 ms 66132 KB Output is correct
5 Correct 39 ms 66288 KB Output is correct
6 Correct 49 ms 66128 KB Output is correct
7 Correct 40 ms 65620 KB Output is correct
8 Correct 497 ms 82448 KB Output is correct
9 Correct 534 ms 82804 KB Output is correct
10 Correct 32 ms 65608 KB Output is correct
11 Correct 374 ms 86312 KB Output is correct
12 Correct 434 ms 86288 KB Output is correct
13 Correct 381 ms 86096 KB Output is correct
14 Correct 32 ms 65620 KB Output is correct
15 Correct 335 ms 82392 KB Output is correct
16 Correct 394 ms 82516 KB Output is correct
17 Correct 407 ms 82964 KB Output is correct
18 Correct 472 ms 83080 KB Output is correct
19 Correct 717 ms 84816 KB Output is correct
20 Correct 703 ms 84564 KB Output is correct
21 Correct 485 ms 82372 KB Output is correct
22 Correct 498 ms 82560 KB Output is correct
23 Correct 472 ms 83304 KB Output is correct
24 Correct 466 ms 83384 KB Output is correct
25 Correct 477 ms 83204 KB Output is correct
26 Correct 554 ms 81940 KB Output is correct
27 Correct 487 ms 82256 KB Output is correct
28 Correct 46 ms 65596 KB Output is correct
29 Correct 216 ms 65876 KB Output is correct
30 Correct 381 ms 66244 KB Output is correct
31 Correct 186 ms 66168 KB Output is correct
32 Correct 113 ms 66000 KB Output is correct
33 Correct 303 ms 66120 KB Output is correct
34 Correct 46 ms 65616 KB Output is correct
35 Correct 2545 ms 82844 KB Output is correct
36 Correct 1543 ms 82748 KB Output is correct
37 Correct 1882 ms 82772 KB Output is correct
38 Correct 40 ms 65720 KB Output is correct
39 Correct 481 ms 86100 KB Output is correct
40 Correct 1419 ms 90428 KB Output is correct
41 Correct 585 ms 86068 KB Output is correct
42 Correct 612 ms 86104 KB Output is correct
43 Correct 42 ms 65616 KB Output is correct
44 Correct 1090 ms 83004 KB Output is correct
45 Correct 508 ms 82516 KB Output is correct
46 Correct 622 ms 82936 KB Output is correct
47 Correct 583 ms 83172 KB Output is correct
48 Correct 2918 ms 85664 KB Output is correct
49 Execution timed out 3558 ms 86972 KB Time limit exceeded
50 Halted 0 ms 0 KB -