oj.uz

Submission #910165

# Submission time Handle Problem Language Result Execution time Memory
910165 2024-01-18T00:49:31 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 88572 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;
vector<array<int, 3>> adj[N];
//0: increasing, 1: decreasing, {ancestor, last weight}
array<int, 3> bl[N][18][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 < 18; 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][17][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 = 17; 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 = 400;
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) {
// 			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});
// 			}
			lst = i - 1;
			upd.clear();
			for (int i = 1; i <= n; i++) {
				for (int j = 0; j <= SZ(adj[i]); j++) {
					dp[i][j] = -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
// 			cout << i << endl;
			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 {
					ans += checkpath(x, a, t - 1, 0);
				}
			}
#ifdef MINA
// 			cout << i << endl;
			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 30 ms 16288 KB Output is correct
2 Correct 34 ms 18840 KB Output is correct
3 Correct 40 ms 19048 KB Output is correct
4 Correct 37 ms 18840 KB Output is correct
5 Correct 33 ms 19024 KB Output is correct
6 Correct 41 ms 19028 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16288 KB Output is correct
2 Correct 34 ms 18840 KB Output is correct
3 Correct 40 ms 19048 KB Output is correct
4 Correct 37 ms 18840 KB Output is correct
5 Correct 33 ms 19024 KB Output is correct
6 Correct 41 ms 19028 KB Output is correct
7 Correct 42 ms 16344 KB Output is correct
8 Correct 218 ms 18772 KB Output is correct
9 Correct 497 ms 19360 KB Output is correct
10 Correct 232 ms 18768 KB Output is correct
11 Correct 247 ms 18868 KB Output is correct
12 Correct 628 ms 19264 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16220 KB Output is correct
2 Correct 314 ms 82596 KB Output is correct
3 Correct 345 ms 82688 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16220 KB Output is correct
2 Correct 314 ms 82596 KB Output is correct
3 Correct 345 ms 82688 KB Output is correct
4 Correct 40 ms 16340 KB Output is correct
5 Correct 1254 ms 88184 KB Output is correct
6 Correct 1321 ms 88452 KB Output is correct
7 Correct 1582 ms 88572 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16220 KB Output is correct
2 Correct 321 ms 86184 KB Output is correct
3 Correct 308 ms 86500 KB Output is correct
4 Correct 330 ms 86124 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16220 KB Output is correct
2 Correct 321 ms 86184 KB Output is correct
3 Correct 308 ms 86500 KB Output is correct
4 Correct 330 ms 86124 KB Output is correct
5 Correct 30 ms 16208 KB Output is correct
6 Correct 455 ms 86096 KB Output is correct
7 Correct 1276 ms 86368 KB Output is correct
8 Correct 560 ms 86144 KB Output is correct
9 Correct 546 ms 86272 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16208 KB Output is correct
2 Correct 268 ms 82468 KB Output is correct
3 Correct 326 ms 82424 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16208 KB Output is correct
2 Correct 268 ms 82468 KB Output is correct
3 Correct 326 ms 82424 KB Output is correct
4 Correct 38 ms 16340 KB Output is correct
5 Correct 1283 ms 83048 KB Output is correct
6 Correct 451 ms 82492 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16324 KB Output is correct
2 Correct 298 ms 86280 KB Output is correct
3 Correct 320 ms 86196 KB Output is correct
4 Correct 338 ms 86352 KB Output is correct
5 Correct 28 ms 16208 KB Output is correct
6 Correct 281 ms 82532 KB Output is correct
7 Correct 314 ms 82516 KB Output is correct
8 Correct 315 ms 83032 KB Output is correct
9 Correct 338 ms 83024 KB Output is correct
10 Correct 523 ms 84820 KB Output is correct
11 Correct 516 ms 84048 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16324 KB Output is correct
2 Correct 298 ms 86280 KB Output is correct
3 Correct 320 ms 86196 KB Output is correct
4 Correct 338 ms 86352 KB Output is correct
5 Correct 28 ms 16208 KB Output is correct
6 Correct 281 ms 82532 KB Output is correct
7 Correct 314 ms 82516 KB Output is correct
8 Correct 315 ms 83032 KB Output is correct
9 Correct 338 ms 83024 KB Output is correct
10 Correct 523 ms 84820 KB Output is correct
11 Correct 516 ms 84048 KB Output is correct
12 Correct 29 ms 16208 KB Output is correct
13 Correct 431 ms 86444 KB Output is correct
14 Correct 1233 ms 86608 KB Output is correct
15 Correct 541 ms 86160 KB Output is correct
16 Correct 541 ms 86460 KB Output is correct
17 Correct 38 ms 16212 KB Output is correct
18 Correct 1265 ms 82568 KB Output is correct
19 Correct 484 ms 82348 KB Output is correct
20 Correct 568 ms 82936 KB Output is correct
21 Correct 490 ms 83028 KB Output is correct
22 Correct 2549 ms 84160 KB Output is correct
23 Execution timed out 3551 ms 85100 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16312 KB Output is correct
2 Correct 36 ms 18728 KB Output is correct
3 Correct 48 ms 18900 KB Output is correct
4 Correct 37 ms 19028 KB Output is correct
5 Correct 33 ms 19032 KB Output is correct
6 Correct 43 ms 18832 KB Output is correct
7 Correct 33 ms 16208 KB Output is correct
8 Correct 323 ms 82552 KB Output is correct
9 Correct 317 ms 82440 KB Output is correct
10 Correct 27 ms 16212 KB Output is correct
11 Correct 308 ms 86328 KB Output is correct
12 Correct 286 ms 86352 KB Output is correct
13 Correct 343 ms 86224 KB Output is correct
14 Correct 28 ms 16220 KB Output is correct
15 Correct 291 ms 82500 KB Output is correct
16 Correct 337 ms 82520 KB Output is correct
17 Correct 307 ms 83028 KB Output is correct
18 Correct 358 ms 83056 KB Output is correct
19 Correct 518 ms 84640 KB Output is correct
20 Correct 522 ms 84128 KB Output is correct
21 Correct 318 ms 82364 KB Output is correct
22 Correct 341 ms 82684 KB Output is correct
23 Correct 344 ms 83024 KB Output is correct
24 Correct 368 ms 83124 KB Output is correct
25 Correct 354 ms 83208 KB Output is correct
26 Correct 384 ms 82256 KB Output is correct
27 Correct 367 ms 82008 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16312 KB Output is correct
2 Correct 36 ms 18728 KB Output is correct
3 Correct 48 ms 18900 KB Output is correct
4 Correct 37 ms 19028 KB Output is correct
5 Correct 33 ms 19032 KB Output is correct
6 Correct 43 ms 18832 KB Output is correct
7 Correct 33 ms 16208 KB Output is correct
8 Correct 323 ms 82552 KB Output is correct
9 Correct 317 ms 82440 KB Output is correct
10 Correct 27 ms 16212 KB Output is correct
11 Correct 308 ms 86328 KB Output is correct
12 Correct 286 ms 86352 KB Output is correct
13 Correct 343 ms 86224 KB Output is correct
14 Correct 28 ms 16220 KB Output is correct
15 Correct 291 ms 82500 KB Output is correct
16 Correct 337 ms 82520 KB Output is correct
17 Correct 307 ms 83028 KB Output is correct
18 Correct 358 ms 83056 KB Output is correct
19 Correct 518 ms 84640 KB Output is correct
20 Correct 522 ms 84128 KB Output is correct
21 Correct 318 ms 82364 KB Output is correct
22 Correct 341 ms 82684 KB Output is correct
23 Correct 344 ms 83024 KB Output is correct
24 Correct 368 ms 83124 KB Output is correct
25 Correct 354 ms 83208 KB Output is correct
26 Correct 384 ms 82256 KB Output is correct
27 Correct 367 ms 82008 KB Output is correct
28 Correct 45 ms 16240 KB Output is correct
29 Correct 205 ms 18680 KB Output is correct
30 Correct 487 ms 19548 KB Output is correct
31 Correct 225 ms 18880 KB Output is correct
32 Correct 255 ms 19008 KB Output is correct
33 Correct 619 ms 19208 KB Output is correct
34 Correct 45 ms 16468 KB Output is correct
35 Correct 1277 ms 88140 KB Output is correct
36 Correct 1578 ms 88504 KB Output is correct
37 Correct 1576 ms 88088 KB Output is correct
38 Correct 35 ms 16216 KB Output is correct
39 Correct 450 ms 86264 KB Output is correct
40 Correct 1283 ms 86516 KB Output is correct
41 Correct 619 ms 86092 KB Output is correct
42 Correct 553 ms 86100 KB Output is correct
43 Correct 38 ms 16216 KB Output is correct
44 Correct 1258 ms 82556 KB Output is correct
45 Correct 452 ms 82444 KB Output is correct
46 Correct 565 ms 82936 KB Output is correct
47 Correct 516 ms 82828 KB Output is correct
48 Correct 2599 ms 84136 KB Output is correct
49 Execution timed out 3532 ms 85008 KB Time limit exceeded
50 Halted 0 ms 0 KB -