oj.uz

Submission #911102

# Submission time Handle Problem Language Result Execution time Memory
911102 2024-01-18T12:56:49 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 89764 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef int64_t ll;
#define SZ(x) (int) x.size()

const int N = 120'005, LOG = 18;
vector<array<int, 3>> adj[N];
//0: increasing, 1: decreasing, {ancestor, last weight}
array<int, 3> bl[N][LOG][2];
int st[N], en[N], curt;
void dfs(int i, int par, int part) {
	bl[i][0][0] = {par, part, part};
	bl[i][0][1] = {par, part, part};
	for (int j = 1; j < LOG; j++) {
		{
			bl[i][j][0] = bl[i][j - 1][0];
			auto [lst, lstt, mx] = bl[i][j][0];
			if (lstt <= bl[lst][0][0][1]) {
				bl[i][j][0] = bl[lst][j - 1][0];
				bl[i][j][0][2] = max(bl[i][j][0][2], mx);
			}
		}
		{
			bl[i][j][1] = bl[i][j - 1][1];
			auto [lst, lstt, mx] = bl[i][j][1];
			if (lstt >= bl[lst][0][1][1]) {
				bl[i][j][1] = bl[lst][j - 1][1];
				bl[i][j][1][2] = max(bl[i][j][1][2], mx);
			}
		}
	}
	st[i] = curt++;
	for (auto [nxt, t, nxtidx] : adj[i]) {
		if (nxt == par) continue;
		dfs(nxt, i, t);
	}
	en[i] = curt;
}
bool isanc(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[a][LOG - 1][t][0];
	if (!isanc(high, b)) {
		return {int(1e9), 0};
	}
	if (a == high || isanc(a, b)) {
		return {int(-1e9), (t == 1? 1 : -1) * int(1e9)};
	}
	for (int j = LOG - 1; j >= 0; j--) {
		if (!isanc(bl[a][j][t][0], b)) {
			mx = max(mx, bl[a][j][t][2]);
			a = bl[a][j][t][0];
		}
	}
	return {max(mx, bl[a][0][t][2]), bl[a][0][t][1]};
}
vector<int> dp[N];
int lst;
int solve(int i, int par) {
	if (~dp[i][par]) return dp[i][par];
	int j = (par == SZ(adj[i])? 0 : par + 1);
	dp[i][par] = 1;
	if (j < SZ(adj[i])) {
		if (adj[i][j][1] > lst) return dp[i][par];
		dp[i][par] += solve(adj[i][j][0], adj[i][j][2]) + solve(i, j) - 1;
	}
	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 = 500;
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	auto S = chrono::steady_clock::now().time_since_epoch().count();
	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);
		for (int j = 0; j <= SZ(adj[i]); j++) {
			dp[i][j] = -1;
		}
	}
	vector<array<int, 3>> upd;
	lst = -1;
	ll s = 0;
	for (int i = 0; i < q; i++) {
		if (upd.size() == B) {
			lst = i - 1;
			upd.clear();
			for (int j = 1; j <= n; j++) {
				for (int k = 0; k <= SZ(adj[j]); k++) {
					dp[j][k] = -1;
				}
			}
		}
		if (v[i].first == 'S') {
			int a = v[i].second[0], b = v[i].second[1];
			if (isanc(b, a)) swap(a, b);
			upd.push_back({a, b, i});
		} else if (v[i].first == 'Q') {
			int a = v[i].second[0], b = v[i].second[1];
#ifdef MINA
			s += (checkpath(a, b, i, 1));
#else
			cout << (checkpath(a, b, i, 1)? "yes\n" : "no\n");
#endif
		} else {
			int x = v[i].second[0];
			int ans = solve(x, adj[x].size());
			for (auto [a, b, t] : upd) {
				if (isanc(b, x)) {
					array<int, 2> val = check(0, x, b);
					ans += val[0] <= t - 1;
				} else if (isanc(a, x)) {
					array<int, 2> val = check(0, x, a);
					ans += val[0] <= t - 1;
				} else {
					ans += checkpath(x, a, t - 1, 0);
				}
			}
#ifdef MINA
			s += ans;
#else
			cout << ans << '\n';
#endif
		}
	}
#ifdef MINA
	cout << s << '\n';
	auto E = chrono::steady_clock::now().time_since_epoch().count();
	cout << (E - S) / 1e9 << "s\n";
#endif
	return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:85:7: warning: unused variable 'S' [-Wunused-variable]
   85 |  auto S = chrono::steady_clock::now().time_since_epoch().count();
      |       ^
servers.cpp:118:5: warning: unused variable 's' [-Wunused-variable]
  118 |  ll s = 0;
      |     ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16980 KB Output is correct
2 Correct 34 ms 19804 KB Output is correct
3 Correct 40 ms 19976 KB Output is correct
4 Correct 43 ms 20068 KB Output is correct
5 Correct 33 ms 20048 KB Output is correct
6 Correct 41 ms 20048 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16980 KB Output is correct
2 Correct 34 ms 19804 KB Output is correct
3 Correct 40 ms 19976 KB Output is correct
4 Correct 43 ms 20068 KB Output is correct
5 Correct 33 ms 20048 KB Output is correct
6 Correct 41 ms 20048 KB Output is correct
7 Correct 42 ms 17124 KB Output is correct
8 Correct 266 ms 19672 KB Output is correct
9 Correct 523 ms 19792 KB Output is correct
10 Correct 254 ms 19856 KB Output is correct
11 Correct 243 ms 19612 KB Output is correct
12 Correct 682 ms 19912 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 16976 KB Output is correct
2 Correct 315 ms 84400 KB Output is correct
3 Correct 301 ms 84292 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 16976 KB Output is correct
2 Correct 315 ms 84400 KB Output is correct
3 Correct 301 ms 84292 KB Output is correct
4 Correct 40 ms 17104 KB Output is correct
5 Correct 936 ms 89764 KB Output is correct
6 Correct 890 ms 89372 KB Output is correct
7 Correct 1287 ms 89664 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16972 KB Output is correct
2 Correct 291 ms 88096 KB Output is correct
3 Correct 286 ms 88148 KB Output is correct
4 Correct 360 ms 88476 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16972 KB Output is correct
2 Correct 291 ms 88096 KB Output is correct
3 Correct 286 ms 88148 KB Output is correct
4 Correct 360 ms 88476 KB Output is correct
5 Correct 29 ms 17088 KB Output is correct
6 Correct 435 ms 87892 KB Output is correct
7 Correct 1228 ms 86596 KB Output is correct
8 Correct 519 ms 86156 KB Output is correct
9 Correct 529 ms 86096 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16356 KB Output is correct
2 Correct 250 ms 82408 KB Output is correct
3 Correct 297 ms 82572 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16356 KB Output is correct
2 Correct 250 ms 82408 KB Output is correct
3 Correct 297 ms 82572 KB Output is correct
4 Correct 39 ms 16196 KB Output is correct
5 Correct 1457 ms 82436 KB Output is correct
6 Correct 515 ms 82488 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16216 KB Output is correct
2 Correct 283 ms 86192 KB Output is correct
3 Correct 283 ms 86188 KB Output is correct
4 Correct 343 ms 86096 KB Output is correct
5 Correct 28 ms 16208 KB Output is correct
6 Correct 250 ms 82512 KB Output is correct
7 Correct 313 ms 82616 KB Output is correct
8 Correct 289 ms 83024 KB Output is correct
9 Correct 344 ms 83280 KB Output is correct
10 Correct 487 ms 84700 KB Output is correct
11 Correct 483 ms 84272 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16216 KB Output is correct
2 Correct 283 ms 86192 KB Output is correct
3 Correct 283 ms 86188 KB Output is correct
4 Correct 343 ms 86096 KB Output is correct
5 Correct 28 ms 16208 KB Output is correct
6 Correct 250 ms 82512 KB Output is correct
7 Correct 313 ms 82616 KB Output is correct
8 Correct 289 ms 83024 KB Output is correct
9 Correct 344 ms 83280 KB Output is correct
10 Correct 487 ms 84700 KB Output is correct
11 Correct 483 ms 84272 KB Output is correct
12 Correct 28 ms 16368 KB Output is correct
13 Correct 423 ms 86356 KB Output is correct
14 Correct 1301 ms 86356 KB Output is correct
15 Correct 548 ms 86356 KB Output is correct
16 Correct 548 ms 86200 KB Output is correct
17 Correct 42 ms 16212 KB Output is correct
18 Correct 1441 ms 82772 KB Output is correct
19 Correct 467 ms 82512 KB Output is correct
20 Correct 647 ms 83208 KB Output is correct
21 Correct 557 ms 83028 KB Output is correct
22 Correct 2883 ms 84332 KB Output is correct
23 Execution timed out 3507 ms 85068 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16212 KB Output is correct
2 Correct 38 ms 18772 KB Output is correct
3 Correct 40 ms 19028 KB Output is correct
4 Correct 37 ms 19024 KB Output is correct
5 Correct 34 ms 19028 KB Output is correct
6 Correct 41 ms 19024 KB Output is correct
7 Correct 32 ms 16212 KB Output is correct
8 Correct 312 ms 82472 KB Output is correct
9 Correct 309 ms 82588 KB Output is correct
10 Correct 27 ms 16224 KB Output is correct
11 Correct 277 ms 86356 KB Output is correct
12 Correct 298 ms 86436 KB Output is correct
13 Correct 344 ms 86096 KB Output is correct
14 Correct 30 ms 16216 KB Output is correct
15 Correct 268 ms 82652 KB Output is correct
16 Correct 321 ms 82384 KB Output is correct
17 Correct 294 ms 82944 KB Output is correct
18 Correct 325 ms 83024 KB Output is correct
19 Correct 488 ms 84624 KB Output is correct
20 Correct 474 ms 84264 KB Output is correct
21 Correct 301 ms 82364 KB Output is correct
22 Correct 321 ms 82600 KB Output is correct
23 Correct 314 ms 83280 KB Output is correct
24 Correct 331 ms 83284 KB Output is correct
25 Correct 316 ms 83152 KB Output is correct
26 Correct 367 ms 81948 KB Output is correct
27 Correct 339 ms 82000 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16212 KB Output is correct
2 Correct 38 ms 18772 KB Output is correct
3 Correct 40 ms 19028 KB Output is correct
4 Correct 37 ms 19024 KB Output is correct
5 Correct 34 ms 19028 KB Output is correct
6 Correct 41 ms 19024 KB Output is correct
7 Correct 32 ms 16212 KB Output is correct
8 Correct 312 ms 82472 KB Output is correct
9 Correct 309 ms 82588 KB Output is correct
10 Correct 27 ms 16224 KB Output is correct
11 Correct 277 ms 86356 KB Output is correct
12 Correct 298 ms 86436 KB Output is correct
13 Correct 344 ms 86096 KB Output is correct
14 Correct 30 ms 16216 KB Output is correct
15 Correct 268 ms 82652 KB Output is correct
16 Correct 321 ms 82384 KB Output is correct
17 Correct 294 ms 82944 KB Output is correct
18 Correct 325 ms 83024 KB Output is correct
19 Correct 488 ms 84624 KB Output is correct
20 Correct 474 ms 84264 KB Output is correct
21 Correct 301 ms 82364 KB Output is correct
22 Correct 321 ms 82600 KB Output is correct
23 Correct 314 ms 83280 KB Output is correct
24 Correct 331 ms 83284 KB Output is correct
25 Correct 316 ms 83152 KB Output is correct
26 Correct 367 ms 81948 KB Output is correct
27 Correct 339 ms 82000 KB Output is correct
28 Correct 44 ms 16216 KB Output is correct
29 Correct 293 ms 19024 KB Output is correct
30 Correct 526 ms 18960 KB Output is correct
31 Correct 251 ms 19052 KB Output is correct
32 Correct 243 ms 19024 KB Output is correct
33 Correct 698 ms 19180 KB Output is correct
34 Correct 39 ms 16376 KB Output is correct
35 Correct 1041 ms 88060 KB Output is correct
36 Correct 1087 ms 88468 KB Output is correct
37 Correct 1356 ms 88148 KB Output is correct
38 Correct 29 ms 16212 KB Output is correct
39 Correct 408 ms 86036 KB Output is correct
40 Correct 1334 ms 86440 KB Output is correct
41 Correct 547 ms 86048 KB Output is correct
42 Correct 569 ms 86440 KB Output is correct
43 Correct 38 ms 16172 KB Output is correct
44 Correct 1433 ms 83056 KB Output is correct
45 Correct 464 ms 82360 KB Output is correct
46 Correct 637 ms 82916 KB Output is correct
47 Correct 567 ms 82992 KB Output is correct
48 Correct 3142 ms 84044 KB Output is correct
49 Execution timed out 3520 ms 85156 KB Time limit exceeded
50 Halted 0 ms 0 KB -