oj.uz

답안 #910107

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
910107 2024-01-17T22:31:05 Z MinaRagy06 Inside information (BOI21_servers) C++17
50 / 100
 3500 ms 90684 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 lca(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 (!lca(high, b)) {
		return {int(1e9), 0};
	}
	if (a == high || lca(a, b)) {
		return {int(-1e9), (t == 1? 1 : -1) * int(1e9)};
	}
	for (int j = 17; j >= 0; j--) {
		if (!lca(bl[t][j][a][0], b) && !lca(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<array<int, 3>> curadj[N];
vector<int> dp[N];
int solve(int i, int par) {
	int prv = -1;
	if (par < SZ(curadj[i])) prv = adj[i][par][1];
	dp[i][par] = 1;
	for (int j = 0; j < SZ(curadj[i]); j++) {
		auto [nxt, t, nxtidx] = curadj[i][j];
		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;
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	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);
	}
	auto recalc = [&] () {
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= SZ(adj[i]); j++) {
				dp[i][j] = -1;
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= SZ(adj[i]); j++) {
				solve(i, j);
			}
		}
	};
	vector<array<int, 3>> upd;
	recalc();
	for (int i = 0; i < q; i++) {
		if (v[i].first == 'S') {
			int a = v[i].second[0], b = v[i].second[1];
// 			int x = curadj[b].size(), y = curadj[a].size();
// 			curadj[a].push_back({b, i, x});
// 			curadj[b].push_back({a, i, y});
			upd.push_back({a, b, i});
		} else if (v[i].first == 'Q') {
			int a = v[i].second[0], b = v[i].second[1];
			cout << (checkpath(a, b, i, 1)? "yes\n" : "no\n");
		} else {
			int x = v[i].second[0];
// 			recalc();
// 			cout << dp[x][adj[x].size()] << '\n';
			int ans = dp[x][adj[x].size()];
			for (auto [a, b, t] : upd) {
				ans += checkpath(x, b, t - 1, 0) || checkpath(x, a, t - 1, 0);
			}
			cout << ans << '\n';
		}
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 68432 KB Output is correct
2 Correct 42 ms 68848 KB Output is correct
3 Correct 48 ms 68948 KB Output is correct
4 Correct 44 ms 69004 KB Output is correct
5 Correct 41 ms 69200 KB Output is correct
6 Correct 53 ms 68944 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 68432 KB Output is correct
2 Correct 42 ms 68848 KB Output is correct
3 Correct 48 ms 68948 KB Output is correct
4 Correct 44 ms 69004 KB Output is correct
5 Correct 41 ms 69200 KB Output is correct
6 Correct 53 ms 68944 KB Output is correct
7 Correct 58 ms 68396 KB Output is correct
8 Correct 3325 ms 69024 KB Output is correct
9 Execution timed out 3519 ms 70212 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 68244 KB Output is correct
2 Correct 339 ms 87512 KB Output is correct
3 Correct 356 ms 87392 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 68244 KB Output is correct
2 Correct 339 ms 87512 KB Output is correct
3 Correct 356 ms 87392 KB Output is correct
4 Correct 71 ms 68692 KB Output is correct
5 Execution timed out 3529 ms 85380 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 68288 KB Output is correct
2 Correct 225 ms 90568 KB Output is correct
3 Correct 223 ms 90604 KB Output is correct
4 Correct 173 ms 90596 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 68288 KB Output is correct
2 Correct 225 ms 90568 KB Output is correct
3 Correct 223 ms 90604 KB Output is correct
4 Correct 173 ms 90596 KB Output is correct
5 Correct 40 ms 68432 KB Output is correct
6 Execution timed out 3546 ms 89580 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 68436 KB Output is correct
2 Correct 171 ms 86744 KB Output is correct
3 Correct 243 ms 86968 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 68436 KB Output is correct
2 Correct 171 ms 86744 KB Output is correct
3 Correct 243 ms 86968 KB Output is correct
4 Correct 53 ms 68440 KB Output is correct
5 Execution timed out 3578 ms 85608 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 68440 KB Output is correct
2 Correct 236 ms 90684 KB Output is correct
3 Correct 214 ms 90572 KB Output is correct
4 Correct 190 ms 90460 KB Output is correct
5 Correct 35 ms 68236 KB Output is correct
6 Correct 164 ms 86732 KB Output is correct
7 Correct 230 ms 86980 KB Output is correct
8 Correct 243 ms 87548 KB Output is correct
9 Correct 292 ms 87248 KB Output is correct
10 Correct 356 ms 88904 KB Output is correct
11 Correct 376 ms 88496 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 68440 KB Output is correct
2 Correct 236 ms 90684 KB Output is correct
3 Correct 214 ms 90572 KB Output is correct
4 Correct 190 ms 90460 KB Output is correct
5 Correct 35 ms 68236 KB Output is correct
6 Correct 164 ms 86732 KB Output is correct
7 Correct 230 ms 86980 KB Output is correct
8 Correct 243 ms 87548 KB Output is correct
9 Correct 292 ms 87248 KB Output is correct
10 Correct 356 ms 88904 KB Output is correct
11 Correct 376 ms 88496 KB Output is correct
12 Correct 40 ms 68432 KB Output is correct
13 Execution timed out 3565 ms 89300 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 68256 KB Output is correct
2 Correct 51 ms 68912 KB Output is correct
3 Correct 50 ms 68944 KB Output is correct
4 Correct 45 ms 69144 KB Output is correct
5 Correct 42 ms 69208 KB Output is correct
6 Correct 51 ms 68976 KB Output is correct
7 Correct 41 ms 68696 KB Output is correct
8 Correct 377 ms 87420 KB Output is correct
9 Correct 380 ms 87440 KB Output is correct
10 Correct 34 ms 68252 KB Output is correct
11 Correct 221 ms 90572 KB Output is correct
12 Correct 267 ms 90608 KB Output is correct
13 Correct 164 ms 90556 KB Output is correct
14 Correct 36 ms 68428 KB Output is correct
15 Correct 170 ms 86732 KB Output is correct
16 Correct 227 ms 86980 KB Output is correct
17 Correct 280 ms 87236 KB Output is correct
18 Correct 317 ms 87436 KB Output is correct
19 Correct 366 ms 89024 KB Output is correct
20 Correct 381 ms 88768 KB Output is correct
21 Correct 319 ms 86736 KB Output is correct
22 Correct 334 ms 86756 KB Output is correct
23 Correct 289 ms 87500 KB Output is correct
24 Correct 317 ms 87504 KB Output is correct
25 Correct 309 ms 87632 KB Output is correct
26 Correct 260 ms 86464 KB Output is correct
27 Correct 274 ms 86520 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 68256 KB Output is correct
2 Correct 51 ms 68912 KB Output is correct
3 Correct 50 ms 68944 KB Output is correct
4 Correct 45 ms 69144 KB Output is correct
5 Correct 42 ms 69208 KB Output is correct
6 Correct 51 ms 68976 KB Output is correct
7 Correct 41 ms 68696 KB Output is correct
8 Correct 377 ms 87420 KB Output is correct
9 Correct 380 ms 87440 KB Output is correct
10 Correct 34 ms 68252 KB Output is correct
11 Correct 221 ms 90572 KB Output is correct
12 Correct 267 ms 90608 KB Output is correct
13 Correct 164 ms 90556 KB Output is correct
14 Correct 36 ms 68428 KB Output is correct
15 Correct 170 ms 86732 KB Output is correct
16 Correct 227 ms 86980 KB Output is correct
17 Correct 280 ms 87236 KB Output is correct
18 Correct 317 ms 87436 KB Output is correct
19 Correct 366 ms 89024 KB Output is correct
20 Correct 381 ms 88768 KB Output is correct
21 Correct 319 ms 86736 KB Output is correct
22 Correct 334 ms 86756 KB Output is correct
23 Correct 289 ms 87500 KB Output is correct
24 Correct 317 ms 87504 KB Output is correct
25 Correct 309 ms 87632 KB Output is correct
26 Correct 260 ms 86464 KB Output is correct
27 Correct 274 ms 86520 KB Output is correct
28 Correct 59 ms 68436 KB Output is correct
29 Correct 3387 ms 69228 KB Output is correct
30 Execution timed out 3528 ms 69972 KB Time limit exceeded
31 Halted 0 ms 0 KB -