oj.uz

답안 #910134

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
910134 2024-01-17T23:54:08 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 90500 KB 
#include <bits/stdc++.h>
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 = 300;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 65620 KB Output is correct
2 Correct 51 ms 65960 KB Output is correct
3 Correct 51 ms 66128 KB Output is correct
4 Correct 47 ms 66168 KB Output is correct
5 Correct 42 ms 66128 KB Output is correct
6 Correct 53 ms 66132 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 65620 KB Output is correct
2 Correct 51 ms 65960 KB Output is correct
3 Correct 51 ms 66128 KB Output is correct
4 Correct 47 ms 66168 KB Output is correct
5 Correct 42 ms 66128 KB Output is correct
6 Correct 53 ms 66132 KB Output is correct
7 Correct 51 ms 65524 KB Output is correct
8 Correct 184 ms 65872 KB Output is correct
9 Correct 346 ms 66760 KB Output is correct
10 Correct 193 ms 66132 KB Output is correct
11 Correct 106 ms 66304 KB Output is correct
12 Correct 260 ms 66656 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 65616 KB Output is correct
2 Correct 570 ms 82452 KB Output is correct
3 Correct 543 ms 82436 KB Output is correct

Subtask #4
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 65616 KB Output is correct
2 Correct 570 ms 82452 KB Output is correct
3 Correct 543 ms 82436 KB Output is correct
4 Correct 49 ms 65616 KB Output is correct
5 Correct 3029 ms 82660 KB Output is correct
6 Correct 1655 ms 83228 KB Output is correct
7 Correct 2108 ms 82688 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 65452 KB Output is correct
2 Correct 419 ms 86352 KB Output is correct
3 Correct 419 ms 86352 KB Output is correct
4 Correct 416 ms 86088 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 65452 KB Output is correct
2 Correct 419 ms 86352 KB Output is correct
3 Correct 419 ms 86352 KB Output is correct
4 Correct 416 ms 86088 KB Output is correct
5 Correct 39 ms 65560 KB Output is correct
6 Correct 536 ms 86216 KB Output is correct
7 Correct 1484 ms 90264 KB Output is correct
8 Correct 620 ms 85980 KB Output is correct
9 Correct 626 ms 86352 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 65628 KB Output is correct
2 Correct 377 ms 82624 KB Output is correct
3 Correct 409 ms 82512 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 65628 KB Output is correct
2 Correct 377 ms 82624 KB Output is correct
3 Correct 409 ms 82512 KB Output is correct
4 Correct 46 ms 65552 KB Output is correct
5 Correct 1128 ms 82740 KB Output is correct
6 Correct 562 ms 82520 KB Output is correct

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 65616 KB Output is correct
2 Correct 408 ms 86200 KB Output is correct
3 Correct 412 ms 86356 KB Output is correct
4 Correct 427 ms 86100 KB Output is correct
5 Correct 36 ms 65692 KB Output is correct
6 Correct 369 ms 82512 KB Output is correct
7 Correct 451 ms 82560 KB Output is correct
8 Correct 419 ms 82844 KB Output is correct
9 Correct 502 ms 83024 KB Output is correct
10 Correct 735 ms 84504 KB Output is correct
11 Correct 733 ms 84264 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 65616 KB Output is correct
2 Correct 408 ms 86200 KB Output is correct
3 Correct 412 ms 86356 KB Output is correct
4 Correct 427 ms 86100 KB Output is correct
5 Correct 36 ms 65692 KB Output is correct
6 Correct 369 ms 82512 KB Output is correct
7 Correct 451 ms 82560 KB Output is correct
8 Correct 419 ms 82844 KB Output is correct
9 Correct 502 ms 83024 KB Output is correct
10 Correct 735 ms 84504 KB Output is correct
11 Correct 733 ms 84264 KB Output is correct
12 Correct 39 ms 65616 KB Output is correct
13 Correct 552 ms 86196 KB Output is correct
14 Correct 1618 ms 90308 KB Output is correct
15 Correct 658 ms 86156 KB Output is correct
16 Correct 707 ms 86036 KB Output is correct
17 Correct 47 ms 65616 KB Output is correct
18 Correct 1283 ms 82668 KB Output is correct
19 Correct 606 ms 82516 KB Output is correct
20 Correct 730 ms 82968 KB Output is correct
21 Correct 688 ms 82992 KB Output is correct
22 Correct 3037 ms 85504 KB Output is correct
23 Execution timed out 3596 ms 86412 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 65620 KB Output is correct
2 Correct 49 ms 66052 KB Output is correct
3 Correct 51 ms 66124 KB Output is correct
4 Correct 48 ms 66132 KB Output is correct
5 Correct 44 ms 66132 KB Output is correct
6 Correct 53 ms 66128 KB Output is correct
7 Correct 40 ms 65616 KB Output is correct
8 Correct 573 ms 82652 KB Output is correct
9 Correct 556 ms 82432 KB Output is correct
10 Correct 35 ms 65620 KB Output is correct
11 Correct 406 ms 86344 KB Output is correct
12 Correct 424 ms 86560 KB Output is correct
13 Correct 407 ms 86144 KB Output is correct
14 Correct 38 ms 65616 KB Output is correct
15 Correct 366 ms 82512 KB Output is correct
16 Correct 440 ms 82772 KB Output is correct
17 Correct 428 ms 83028 KB Output is correct
18 Correct 494 ms 83020 KB Output is correct
19 Correct 755 ms 84632 KB Output is correct
20 Correct 745 ms 84268 KB Output is correct
21 Correct 544 ms 82528 KB Output is correct
22 Correct 535 ms 82488 KB Output is correct
23 Correct 529 ms 83376 KB Output is correct
24 Correct 499 ms 83284 KB Output is correct
25 Correct 526 ms 83180 KB Output is correct
26 Correct 587 ms 82288 KB Output is correct
27 Correct 532 ms 81948 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 65620 KB Output is correct
2 Correct 49 ms 66052 KB Output is correct
3 Correct 51 ms 66124 KB Output is correct
4 Correct 48 ms 66132 KB Output is correct
5 Correct 44 ms 66132 KB Output is correct
6 Correct 53 ms 66128 KB Output is correct
7 Correct 40 ms 65616 KB Output is correct
8 Correct 573 ms 82652 KB Output is correct
9 Correct 556 ms 82432 KB Output is correct
10 Correct 35 ms 65620 KB Output is correct
11 Correct 406 ms 86344 KB Output is correct
12 Correct 424 ms 86560 KB Output is correct
13 Correct 407 ms 86144 KB Output is correct
14 Correct 38 ms 65616 KB Output is correct
15 Correct 366 ms 82512 KB Output is correct
16 Correct 440 ms 82772 KB Output is correct
17 Correct 428 ms 83028 KB Output is correct
18 Correct 494 ms 83020 KB Output is correct
19 Correct 755 ms 84632 KB Output is correct
20 Correct 745 ms 84268 KB Output is correct
21 Correct 544 ms 82528 KB Output is correct
22 Correct 535 ms 82488 KB Output is correct
23 Correct 529 ms 83376 KB Output is correct
24 Correct 499 ms 83284 KB Output is correct
25 Correct 526 ms 83180 KB Output is correct
26 Correct 587 ms 82288 KB Output is correct
27 Correct 532 ms 81948 KB Output is correct
28 Correct 51 ms 65616 KB Output is correct
29 Correct 184 ms 65872 KB Output is correct
30 Correct 340 ms 66708 KB Output is correct
31 Correct 198 ms 65960 KB Output is correct
32 Correct 105 ms 66152 KB Output is correct
33 Correct 254 ms 66200 KB Output is correct
34 Correct 51 ms 65620 KB Output is correct
35 Correct 3075 ms 82944 KB Output is correct
36 Correct 1600 ms 83200 KB Output is correct
37 Correct 1840 ms 82832 KB Output is correct
38 Correct 39 ms 65628 KB Output is correct
39 Correct 524 ms 86224 KB Output is correct
40 Correct 1471 ms 90500 KB Output is correct
41 Correct 627 ms 86388 KB Output is correct
42 Correct 611 ms 86100 KB Output is correct
43 Correct 46 ms 65364 KB Output is correct
44 Correct 1128 ms 82708 KB Output is correct
45 Correct 556 ms 82700 KB Output is correct
46 Correct 697 ms 82740 KB Output is correct
47 Correct 639 ms 82804 KB Output is correct
48 Correct 2827 ms 86076 KB Output is correct
49 Execution timed out 3549 ms 86632 KB Time limit exceeded
50 Halted 0 ms 0 KB -