Submission #910111

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
910111	2024-01-17T22:46:52 Z	MinaRagy06	Inside information (BOI21_servers)	C++17	5 / 100	3500 ms	91876 KB

servers

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-

Submission #910111

Compilation message