oj.uz

Submission #910105

# Submission time Handle Problem Language Result Execution time Memory
910105 2024-01-17T22:28:36 Z MinaRagy06 Inside information (BOI21_servers) C++17
50 / 100
 366 ms 90976 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;
	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';
			for (auto [a, b, t] : upd) {
				
			}
		}
	}
	return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:136:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  136 |    for (auto [a, b, t] : upd) {
      |              ^~~~~~~~~
servers.cpp:133:8: warning: unused variable 'x' [-Wunused-variable]
  133 |    int x = v[i].second[0];
      |        ^
servers.cpp:109:7: warning: variable 'recalc' set but not used [-Wunused-but-set-variable]
  109 |  auto recalc = [&] () {
      |       ^~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 68436 KB Output is correct
2 Correct 41 ms 68956 KB Output is correct
3 Correct 48 ms 68996 KB Output is correct
4 Correct 46 ms 68944 KB Output is correct
5 Correct 41 ms 69088 KB Output is correct
6 Correct 51 ms 69052 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 68436 KB Output is correct
2 Correct 41 ms 68956 KB Output is correct
3 Correct 48 ms 68996 KB Output is correct
4 Correct 46 ms 68944 KB Output is correct
5 Correct 41 ms 69088 KB Output is correct
6 Correct 51 ms 69052 KB Output is correct
7 Incorrect 38 ms 68180 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 68404 KB Output is correct
2 Correct 335 ms 87460 KB Output is correct
3 Correct 334 ms 87412 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 68404 KB Output is correct
2 Correct 335 ms 87460 KB Output is correct
3 Correct 334 ms 87412 KB Output is correct
4 Incorrect 39 ms 68432 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 68436 KB Output is correct
2 Correct 211 ms 90556 KB Output is correct
3 Correct 211 ms 90568 KB Output is correct
4 Correct 163 ms 90500 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 68436 KB Output is correct
2 Correct 211 ms 90556 KB Output is correct
3 Correct 211 ms 90568 KB Output is correct
4 Correct 163 ms 90500 KB Output is correct
5 Incorrect 34 ms 68444 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 68300 KB Output is correct
2 Correct 190 ms 86896 KB Output is correct
3 Correct 215 ms 86980 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 68300 KB Output is correct
2 Correct 190 ms 86896 KB Output is correct
3 Correct 215 ms 86980 KB Output is correct
4 Incorrect 36 ms 68260 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 68332 KB Output is correct
2 Correct 221 ms 90976 KB Output is correct
3 Correct 221 ms 90636 KB Output is correct
4 Correct 158 ms 90564 KB Output is correct
5 Correct 36 ms 68432 KB Output is correct
6 Correct 164 ms 86716 KB Output is correct
7 Correct 253 ms 86932 KB Output is correct
8 Correct 235 ms 87236 KB Output is correct
9 Correct 296 ms 87260 KB Output is correct
10 Correct 352 ms 89180 KB Output is correct
11 Correct 366 ms 88440 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 68332 KB Output is correct
2 Correct 221 ms 90976 KB Output is correct
3 Correct 221 ms 90636 KB Output is correct
4 Correct 158 ms 90564 KB Output is correct
5 Correct 36 ms 68432 KB Output is correct
6 Correct 164 ms 86716 KB Output is correct
7 Correct 253 ms 86932 KB Output is correct
8 Correct 235 ms 87236 KB Output is correct
9 Correct 296 ms 87260 KB Output is correct
10 Correct 352 ms 89180 KB Output is correct
11 Correct 366 ms 88440 KB Output is correct
12 Incorrect 35 ms 68176 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 68436 KB Output is correct
2 Correct 44 ms 68944 KB Output is correct
3 Correct 48 ms 69100 KB Output is correct
4 Correct 45 ms 68948 KB Output is correct
5 Correct 40 ms 69072 KB Output is correct
6 Correct 55 ms 69264 KB Output is correct
7 Correct 49 ms 68436 KB Output is correct
8 Correct 333 ms 87304 KB Output is correct
9 Correct 342 ms 87444 KB Output is correct
10 Correct 34 ms 68432 KB Output is correct
11 Correct 207 ms 90728 KB Output is correct
12 Correct 240 ms 90872 KB Output is correct
13 Correct 172 ms 90576 KB Output is correct
14 Correct 36 ms 68432 KB Output is correct
15 Correct 173 ms 86908 KB Output is correct
16 Correct 217 ms 86940 KB Output is correct
17 Correct 243 ms 87168 KB Output is correct
18 Correct 297 ms 87264 KB Output is correct
19 Correct 366 ms 89024 KB Output is correct
20 Correct 347 ms 88648 KB Output is correct
21 Correct 335 ms 86844 KB Output is correct
22 Correct 308 ms 86812 KB Output is correct
23 Correct 294 ms 87496 KB Output is correct
24 Correct 354 ms 87728 KB Output is correct
25 Correct 336 ms 87404 KB Output is correct
26 Correct 297 ms 86304 KB Output is correct
27 Correct 245 ms 86348 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 68436 KB Output is correct
2 Correct 44 ms 68944 KB Output is correct
3 Correct 48 ms 69100 KB Output is correct
4 Correct 45 ms 68948 KB Output is correct
5 Correct 40 ms 69072 KB Output is correct
6 Correct 55 ms 69264 KB Output is correct
7 Correct 49 ms 68436 KB Output is correct
8 Correct 333 ms 87304 KB Output is correct
9 Correct 342 ms 87444 KB Output is correct
10 Correct 34 ms 68432 KB Output is correct
11 Correct 207 ms 90728 KB Output is correct
12 Correct 240 ms 90872 KB Output is correct
13 Correct 172 ms 90576 KB Output is correct
14 Correct 36 ms 68432 KB Output is correct
15 Correct 173 ms 86908 KB Output is correct
16 Correct 217 ms 86940 KB Output is correct
17 Correct 243 ms 87168 KB Output is correct
18 Correct 297 ms 87264 KB Output is correct
19 Correct 366 ms 89024 KB Output is correct
20 Correct 347 ms 88648 KB Output is correct
21 Correct 335 ms 86844 KB Output is correct
22 Correct 308 ms 86812 KB Output is correct
23 Correct 294 ms 87496 KB Output is correct
24 Correct 354 ms 87728 KB Output is correct
25 Correct 336 ms 87404 KB Output is correct
26 Correct 297 ms 86304 KB Output is correct
27 Correct 245 ms 86348 KB Output is correct
28 Incorrect 45 ms 68172 KB Extra information in the output file
29 Halted 0 ms 0 KB -