oj.uz

Submission #910106

# Submission time Handle Problem Language Result Execution time Memory
910106 2024-01-17T22:28:55 Z MinaRagy06 Inside information (BOI21_servers) C++17
50 / 100
 384 ms 91028 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(b, a, i, 0)? "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 39 ms 68436 KB Output is correct
2 Correct 44 ms 68944 KB Output is correct
3 Correct 67 ms 69176 KB Output is correct
4 Correct 45 ms 68948 KB Output is correct
5 Correct 42 ms 69140 KB Output is correct
6 Correct 50 ms 68944 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68436 KB Output is correct
2 Correct 44 ms 68944 KB Output is correct
3 Correct 67 ms 69176 KB Output is correct
4 Correct 45 ms 68948 KB Output is correct
5 Correct 42 ms 69140 KB Output is correct
6 Correct 50 ms 68944 KB Output is correct
7 Incorrect 40 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 68444 KB Output is correct
2 Correct 344 ms 87416 KB Output is correct
3 Correct 339 ms 87352 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 68444 KB Output is correct
2 Correct 344 ms 87416 KB Output is correct
3 Correct 339 ms 87352 KB Output is correct
4 Incorrect 44 ms 68688 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 38 ms 68388 KB Output is correct
2 Correct 220 ms 90568 KB Output is correct
3 Correct 208 ms 90568 KB Output is correct
4 Correct 168 ms 90568 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68388 KB Output is correct
2 Correct 220 ms 90568 KB Output is correct
3 Correct 208 ms 90568 KB Output is correct
4 Correct 168 ms 90568 KB Output is correct
5 Incorrect 42 ms 68176 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 37 ms 68436 KB Output is correct
2 Correct 169 ms 86732 KB Output is correct
3 Correct 226 ms 86984 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 68436 KB Output is correct
2 Correct 169 ms 86732 KB Output is correct
3 Correct 226 ms 86984 KB Output is correct
4 Incorrect 36 ms 68176 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 35 ms 68436 KB Output is correct
2 Correct 227 ms 90792 KB Output is correct
3 Correct 210 ms 90796 KB Output is correct
4 Correct 169 ms 90568 KB Output is correct
5 Correct 36 ms 68432 KB Output is correct
6 Correct 190 ms 86732 KB Output is correct
7 Correct 258 ms 86976 KB Output is correct
8 Correct 253 ms 87208 KB Output is correct
9 Correct 290 ms 87524 KB Output is correct
10 Correct 351 ms 89020 KB Output is correct
11 Correct 384 ms 88692 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 68436 KB Output is correct
2 Correct 227 ms 90792 KB Output is correct
3 Correct 210 ms 90796 KB Output is correct
4 Correct 169 ms 90568 KB Output is correct
5 Correct 36 ms 68432 KB Output is correct
6 Correct 190 ms 86732 KB Output is correct
7 Correct 258 ms 86976 KB Output is correct
8 Correct 253 ms 87208 KB Output is correct
9 Correct 290 ms 87524 KB Output is correct
10 Correct 351 ms 89020 KB Output is correct
11 Correct 384 ms 88692 KB Output is correct
12 Incorrect 39 ms 68692 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 44 ms 68432 KB Output is correct
2 Correct 44 ms 69068 KB Output is correct
3 Correct 49 ms 68968 KB Output is correct
4 Correct 45 ms 68980 KB Output is correct
5 Correct 41 ms 69120 KB Output is correct
6 Correct 55 ms 69100 KB Output is correct
7 Correct 40 ms 68428 KB Output is correct
8 Correct 329 ms 87320 KB Output is correct
9 Correct 355 ms 87420 KB Output is correct
10 Correct 35 ms 68432 KB Output is correct
11 Correct 211 ms 91028 KB Output is correct
12 Correct 211 ms 90824 KB Output is correct
13 Correct 175 ms 90520 KB Output is correct
14 Correct 36 ms 68432 KB Output is correct
15 Correct 175 ms 86732 KB Output is correct
16 Correct 221 ms 86872 KB Output is correct
17 Correct 240 ms 87204 KB Output is correct
18 Correct 285 ms 87532 KB Output is correct
19 Correct 354 ms 89036 KB Output is correct
20 Correct 348 ms 88512 KB Output is correct
21 Correct 324 ms 87024 KB Output is correct
22 Correct 314 ms 86904 KB Output is correct
23 Correct 303 ms 87500 KB Output is correct
24 Correct 279 ms 87500 KB Output is correct
25 Correct 309 ms 87400 KB Output is correct
26 Correct 252 ms 86464 KB Output is correct
27 Correct 234 ms 86448 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 68432 KB Output is correct
2 Correct 44 ms 69068 KB Output is correct
3 Correct 49 ms 68968 KB Output is correct
4 Correct 45 ms 68980 KB Output is correct
5 Correct 41 ms 69120 KB Output is correct
6 Correct 55 ms 69100 KB Output is correct
7 Correct 40 ms 68428 KB Output is correct
8 Correct 329 ms 87320 KB Output is correct
9 Correct 355 ms 87420 KB Output is correct
10 Correct 35 ms 68432 KB Output is correct
11 Correct 211 ms 91028 KB Output is correct
12 Correct 211 ms 90824 KB Output is correct
13 Correct 175 ms 90520 KB Output is correct
14 Correct 36 ms 68432 KB Output is correct
15 Correct 175 ms 86732 KB Output is correct
16 Correct 221 ms 86872 KB Output is correct
17 Correct 240 ms 87204 KB Output is correct
18 Correct 285 ms 87532 KB Output is correct
19 Correct 354 ms 89036 KB Output is correct
20 Correct 348 ms 88512 KB Output is correct
21 Correct 324 ms 87024 KB Output is correct
22 Correct 314 ms 86904 KB Output is correct
23 Correct 303 ms 87500 KB Output is correct
24 Correct 279 ms 87500 KB Output is correct
25 Correct 309 ms 87400 KB Output is correct
26 Correct 252 ms 86464 KB Output is correct
27 Correct 234 ms 86448 KB Output is correct
28 Incorrect 42 ms 68392 KB Extra information in the output file
29 Halted 0 ms 0 KB -