oj.uz

답안 #910111

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
910111 2024-01-17T22:46:52 Z MinaRagy06 Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 91876 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;
	}
}
const int B = 150;
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 (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});
			}
			upd.clear();
			recalc();
		}
		if (v[i].first == 'S') {
			int a = v[i].second[0], b = v[i].second[1];
			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];
			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 36 ms 68240 KB Output is correct
2 Correct 55 ms 68972 KB Output is correct
3 Correct 299 ms 69204 KB Output is correct
4 Correct 61 ms 69204 KB Output is correct
5 Correct 47 ms 69200 KB Output is correct
6 Correct 2771 ms 69312 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 68240 KB Output is correct
2 Correct 55 ms 68972 KB Output is correct
3 Correct 299 ms 69204 KB Output is correct
4 Correct 61 ms 69204 KB Output is correct
5 Correct 47 ms 69200 KB Output is correct
6 Correct 2771 ms 69312 KB Output is correct
7 Correct 54 ms 68316 KB Output is correct
8 Correct 172 ms 68944 KB Output is correct
9 Correct 634 ms 69292 KB Output is correct
10 Correct 198 ms 69280 KB Output is correct
11 Correct 161 ms 68948 KB Output is correct
12 Correct 3015 ms 69244 KB Output is correct

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 68436 KB Output is correct
2 Execution timed out 3592 ms 85116 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 68436 KB Output is correct
2 Execution timed out 3592 ms 85116 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 68388 KB Output is correct
2 Execution timed out 3570 ms 91600 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 68388 KB Output is correct
2 Execution timed out 3570 ms 91600 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 68440 KB Output is correct
2 Execution timed out 3511 ms 89104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 68440 KB Output is correct
2 Execution timed out 3511 ms 89104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 68432 KB Output is correct
2 Execution timed out 3526 ms 91876 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 68432 KB Output is correct
2 Execution timed out 3526 ms 91876 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 68432 KB Output is correct
2 Correct 57 ms 68948 KB Output is correct
3 Correct 290 ms 69444 KB Output is correct
4 Correct 56 ms 69204 KB Output is correct
5 Correct 46 ms 69200 KB Output is correct
6 Correct 2731 ms 69192 KB Output is correct
7 Correct 39 ms 68296 KB Output is correct
8 Execution timed out 3539 ms 85012 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 68432 KB Output is correct
2 Correct 57 ms 68948 KB Output is correct
3 Correct 290 ms 69444 KB Output is correct
4 Correct 56 ms 69204 KB Output is correct
5 Correct 46 ms 69200 KB Output is correct
6 Correct 2731 ms 69192 KB Output is correct
7 Correct 39 ms 68296 KB Output is correct
8 Execution timed out 3539 ms 85012 KB Time limit exceeded
9 Halted 0 ms 0 KB -