oj.uz

답안 #910114

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
910114 2024-01-17T22:56:11 Z MinaRagy06 Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 92296 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) {
  	if (~dp[i][par]) return dp[i][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 = 200;
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 68432 KB Output is correct
2 Correct 45 ms 69148 KB Output is correct
3 Correct 93 ms 69200 KB Output is correct
4 Correct 49 ms 69204 KB Output is correct
5 Correct 45 ms 69236 KB Output is correct
6 Correct 702 ms 69056 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 68432 KB Output is correct
2 Correct 45 ms 69148 KB Output is correct
3 Correct 93 ms 69200 KB Output is correct
4 Correct 49 ms 69204 KB Output is correct
5 Correct 45 ms 69236 KB Output is correct
6 Correct 702 ms 69056 KB Output is correct
7 Correct 57 ms 68404 KB Output is correct
8 Correct 207 ms 69044 KB Output is correct
9 Correct 458 ms 69204 KB Output is correct
10 Correct 232 ms 69016 KB Output is correct
11 Correct 271 ms 69200 KB Output is correct
12 Correct 1257 ms 69244 KB Output is correct

Subtask #3
0 / 2.5

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

Subtask #4
0 / 2.5

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 68444 KB Output is correct
2 Execution timed out 3555 ms 90656 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 68444 KB Output is correct
2 Execution timed out 3555 ms 90656 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 68436 KB Output is correct
2 Correct 47 ms 68944 KB Output is correct
3 Correct 103 ms 69044 KB Output is correct
4 Correct 48 ms 69200 KB Output is correct
5 Correct 44 ms 69204 KB Output is correct
6 Correct 648 ms 69204 KB Output is correct
7 Correct 39 ms 68440 KB Output is correct
8 Execution timed out 3517 ms 85036 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 68436 KB Output is correct
2 Correct 47 ms 68944 KB Output is correct
3 Correct 103 ms 69044 KB Output is correct
4 Correct 48 ms 69200 KB Output is correct
5 Correct 44 ms 69204 KB Output is correct
6 Correct 648 ms 69204 KB Output is correct
7 Correct 39 ms 68440 KB Output is correct
8 Execution timed out 3517 ms 85036 KB Time limit exceeded
9 Halted 0 ms 0 KB -