Submission #910114

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
910114	2024-01-17T22:56:11 Z	MinaRagy06	Inside information (BOI21_servers)	C++17	5 / 100	3500 ms	92296 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) {
  	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

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

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

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

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

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

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

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

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

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

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

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

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

Submission #910114

Compilation message