oj.uz

답안 #910141

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
910141 2024-01-18T00:07:57 Z MinaRagy06 Inside information (BOI21_servers) C++17
67.5 / 100
 3500 ms 90312 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[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 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:87:7: warning: unused variable 'S' [-Wunused-variable]
   87 |  auto S = chrono::steady_clock::now().time_since_epoch().count();
      |       ^
servers.cpp:120:5: warning: unused variable 's' [-Wunused-variable]
  120 |  ll s = 0;
      |     ^

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 16376 KB Output is correct
2 Correct 38 ms 18892 KB Output is correct
3 Correct 39 ms 18932 KB Output is correct
4 Correct 37 ms 18828 KB Output is correct
5 Correct 40 ms 19020 KB Output is correct
6 Correct 51 ms 19024 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 16376 KB Output is correct
2 Correct 38 ms 18892 KB Output is correct
3 Correct 39 ms 18932 KB Output is correct
4 Correct 37 ms 18828 KB Output is correct
5 Correct 40 ms 19020 KB Output is correct
6 Correct 51 ms 19024 KB Output is correct
7 Correct 63 ms 16220 KB Output is correct
8 Correct 205 ms 19024 KB Output is correct
9 Correct 397 ms 19028 KB Output is correct
10 Correct 229 ms 18772 KB Output is correct
11 Correct 133 ms 19028 KB Output is correct
12 Correct 315 ms 19024 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 16220 KB Output is correct
2 Correct 445 ms 82524 KB Output is correct
3 Correct 377 ms 82432 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 16220 KB Output is correct
2 Correct 445 ms 82524 KB Output is correct
3 Correct 377 ms 82432 KB Output is correct
4 Correct 41 ms 16208 KB Output is correct
5 Execution timed out 3549 ms 82720 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 16220 KB Output is correct
2 Correct 387 ms 86312 KB Output is correct
3 Correct 433 ms 86356 KB Output is correct
4 Correct 518 ms 86196 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 16220 KB Output is correct
2 Correct 387 ms 86312 KB Output is correct
3 Correct 433 ms 86356 KB Output is correct
4 Correct 518 ms 86196 KB Output is correct
5 Correct 29 ms 16220 KB Output is correct
6 Correct 540 ms 86200 KB Output is correct
7 Correct 1957 ms 90132 KB Output is correct
8 Correct 825 ms 86240 KB Output is correct
9 Correct 659 ms 86224 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 16220 KB Output is correct
2 Correct 343 ms 82592 KB Output is correct
3 Correct 465 ms 82476 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 16220 KB Output is correct
2 Correct 343 ms 82592 KB Output is correct
3 Correct 465 ms 82476 KB Output is correct
4 Correct 37 ms 16172 KB Output is correct
5 Correct 1329 ms 82600 KB Output is correct
6 Correct 631 ms 82768 KB Output is correct

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 16216 KB Output is correct
2 Correct 401 ms 86152 KB Output is correct
3 Correct 380 ms 86360 KB Output is correct
4 Correct 481 ms 86616 KB Output is correct
5 Correct 32 ms 16372 KB Output is correct
6 Correct 362 ms 82340 KB Output is correct
7 Correct 455 ms 82420 KB Output is correct
8 Correct 446 ms 83040 KB Output is correct
9 Correct 425 ms 83064 KB Output is correct
10 Correct 672 ms 84504 KB Output is correct
11 Correct 611 ms 84260 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 16216 KB Output is correct
2 Correct 401 ms 86152 KB Output is correct
3 Correct 380 ms 86360 KB Output is correct
4 Correct 481 ms 86616 KB Output is correct
5 Correct 32 ms 16372 KB Output is correct
6 Correct 362 ms 82340 KB Output is correct
7 Correct 455 ms 82420 KB Output is correct
8 Correct 446 ms 83040 KB Output is correct
9 Correct 425 ms 83064 KB Output is correct
10 Correct 672 ms 84504 KB Output is correct
11 Correct 611 ms 84260 KB Output is correct
12 Correct 28 ms 16212 KB Output is correct
13 Correct 551 ms 86496 KB Output is correct
14 Correct 1835 ms 90312 KB Output is correct
15 Correct 718 ms 86120 KB Output is correct
16 Correct 855 ms 86332 KB Output is correct
17 Correct 37 ms 16364 KB Output is correct
18 Correct 1179 ms 82344 KB Output is correct
19 Correct 627 ms 82448 KB Output is correct
20 Correct 666 ms 82944 KB Output is correct
21 Correct 628 ms 83092 KB Output is correct
22 Correct 3140 ms 85568 KB Output is correct
23 Execution timed out 3527 ms 86248 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 16220 KB Output is correct
2 Correct 35 ms 18884 KB Output is correct
3 Correct 45 ms 19024 KB Output is correct
4 Correct 47 ms 18864 KB Output is correct
5 Correct 34 ms 19032 KB Output is correct
6 Correct 58 ms 18908 KB Output is correct
7 Correct 32 ms 16220 KB Output is correct
8 Correct 437 ms 82596 KB Output is correct
9 Correct 409 ms 82432 KB Output is correct
10 Correct 31 ms 16396 KB Output is correct
11 Correct 435 ms 86300 KB Output is correct
12 Correct 337 ms 86292 KB Output is correct
13 Correct 481 ms 86096 KB Output is correct
14 Correct 31 ms 16216 KB Output is correct
15 Correct 320 ms 82404 KB Output is correct
16 Correct 426 ms 82788 KB Output is correct
17 Correct 415 ms 83024 KB Output is correct
18 Correct 459 ms 83024 KB Output is correct
19 Correct 642 ms 84768 KB Output is correct
20 Correct 598 ms 84316 KB Output is correct
21 Correct 458 ms 82564 KB Output is correct
22 Correct 429 ms 82616 KB Output is correct
23 Correct 401 ms 83036 KB Output is correct
24 Correct 477 ms 83256 KB Output is correct
25 Correct 453 ms 83648 KB Output is correct
26 Correct 492 ms 82004 KB Output is correct
27 Correct 444 ms 81948 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 16220 KB Output is correct
2 Correct 35 ms 18884 KB Output is correct
3 Correct 45 ms 19024 KB Output is correct
4 Correct 47 ms 18864 KB Output is correct
5 Correct 34 ms 19032 KB Output is correct
6 Correct 58 ms 18908 KB Output is correct
7 Correct 32 ms 16220 KB Output is correct
8 Correct 437 ms 82596 KB Output is correct
9 Correct 409 ms 82432 KB Output is correct
10 Correct 31 ms 16396 KB Output is correct
11 Correct 435 ms 86300 KB Output is correct
12 Correct 337 ms 86292 KB Output is correct
13 Correct 481 ms 86096 KB Output is correct
14 Correct 31 ms 16216 KB Output is correct
15 Correct 320 ms 82404 KB Output is correct
16 Correct 426 ms 82788 KB Output is correct
17 Correct 415 ms 83024 KB Output is correct
18 Correct 459 ms 83024 KB Output is correct
19 Correct 642 ms 84768 KB Output is correct
20 Correct 598 ms 84316 KB Output is correct
21 Correct 458 ms 82564 KB Output is correct
22 Correct 429 ms 82616 KB Output is correct
23 Correct 401 ms 83036 KB Output is correct
24 Correct 477 ms 83256 KB Output is correct
25 Correct 453 ms 83648 KB Output is correct
26 Correct 492 ms 82004 KB Output is correct
27 Correct 444 ms 81948 KB Output is correct
28 Correct 43 ms 16220 KB Output is correct
29 Correct 229 ms 18808 KB Output is correct
30 Correct 379 ms 19028 KB Output is correct
31 Correct 204 ms 18772 KB Output is correct
32 Correct 141 ms 19092 KB Output is correct
33 Correct 331 ms 19028 KB Output is correct
34 Correct 61 ms 16392 KB Output is correct
35 Execution timed out 3529 ms 82716 KB Time limit exceeded
36 Halted 0 ms 0 KB -