oj.uz

Submission #911137

# Submission time Handle Problem Language Result Execution time Memory
911137 2024-01-18T13:31:46 Z MinaRagy06 Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 90416 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, B = 700;
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;
	}
}
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:84:7: warning: unused variable 'S' [-Wunused-variable]
   84 |  auto S = chrono::steady_clock::now().time_since_epoch().count();
      |       ^
servers.cpp:117:5: warning: unused variable 's' [-Wunused-variable]
  117 |  ll s = 0;
      |     ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16212 KB Output is correct
2 Correct 34 ms 18992 KB Output is correct
3 Correct 39 ms 19024 KB Output is correct
4 Correct 37 ms 18952 KB Output is correct
5 Correct 34 ms 19036 KB Output is correct
6 Correct 45 ms 18988 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16212 KB Output is correct
2 Correct 34 ms 18992 KB Output is correct
3 Correct 39 ms 19024 KB Output is correct
4 Correct 37 ms 18952 KB Output is correct
5 Correct 34 ms 19036 KB Output is correct
6 Correct 45 ms 18988 KB Output is correct
7 Correct 43 ms 16352 KB Output is correct
8 Correct 335 ms 18772 KB Output is correct
9 Correct 745 ms 19084 KB Output is correct
10 Correct 349 ms 19024 KB Output is correct
11 Correct 247 ms 19024 KB Output is correct
12 Correct 716 ms 19292 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16208 KB Output is correct
2 Correct 275 ms 82536 KB Output is correct
3 Correct 272 ms 82496 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16208 KB Output is correct
2 Correct 275 ms 82536 KB Output is correct
3 Correct 272 ms 82496 KB Output is correct
4 Correct 40 ms 16220 KB Output is correct
5 Correct 918 ms 88104 KB Output is correct
6 Correct 977 ms 88396 KB Output is correct
7 Correct 1490 ms 88412 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16208 KB Output is correct
2 Correct 250 ms 86356 KB Output is correct
3 Correct 265 ms 86216 KB Output is correct
4 Correct 292 ms 86348 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16208 KB Output is correct
2 Correct 250 ms 86356 KB Output is correct
3 Correct 265 ms 86216 KB Output is correct
4 Correct 292 ms 86348 KB Output is correct
5 Correct 39 ms 17232 KB Output is correct
6 Correct 452 ms 89168 KB Output is correct
7 Correct 1343 ms 89712 KB Output is correct
8 Correct 602 ms 89028 KB Output is correct
9 Correct 619 ms 88652 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16300 KB Output is correct
2 Correct 218 ms 82468 KB Output is correct
3 Correct 268 ms 82428 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16300 KB Output is correct
2 Correct 218 ms 82468 KB Output is correct
3 Correct 268 ms 82428 KB Output is correct
4 Correct 38 ms 16208 KB Output is correct
5 Correct 1223 ms 82776 KB Output is correct
6 Correct 525 ms 82444 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16220 KB Output is correct
2 Correct 252 ms 86148 KB Output is correct
3 Correct 253 ms 86236 KB Output is correct
4 Correct 312 ms 86316 KB Output is correct
5 Correct 30 ms 17244 KB Output is correct
6 Correct 232 ms 85760 KB Output is correct
7 Correct 319 ms 85844 KB Output is correct
8 Correct 279 ms 86352 KB Output is correct
9 Correct 336 ms 86120 KB Output is correct
10 Correct 447 ms 88112 KB Output is correct
11 Correct 415 ms 87380 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16220 KB Output is correct
2 Correct 252 ms 86148 KB Output is correct
3 Correct 253 ms 86236 KB Output is correct
4 Correct 312 ms 86316 KB Output is correct
5 Correct 30 ms 17244 KB Output is correct
6 Correct 232 ms 85760 KB Output is correct
7 Correct 319 ms 85844 KB Output is correct
8 Correct 279 ms 86352 KB Output is correct
9 Correct 336 ms 86120 KB Output is correct
10 Correct 447 ms 88112 KB Output is correct
11 Correct 415 ms 87380 KB Output is correct
12 Correct 30 ms 17232 KB Output is correct
13 Correct 474 ms 89172 KB Output is correct
14 Correct 1434 ms 89780 KB Output is correct
15 Correct 672 ms 88968 KB Output is correct
16 Correct 707 ms 88884 KB Output is correct
17 Correct 39 ms 17240 KB Output is correct
18 Correct 1268 ms 85564 KB Output is correct
19 Correct 571 ms 85072 KB Output is correct
20 Correct 628 ms 85548 KB Output is correct
21 Correct 654 ms 85500 KB Output is correct
22 Execution timed out 3536 ms 86308 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16220 KB Output is correct
2 Correct 35 ms 18780 KB Output is correct
3 Correct 44 ms 19028 KB Output is correct
4 Correct 38 ms 19024 KB Output is correct
5 Correct 49 ms 19036 KB Output is correct
6 Correct 39 ms 18824 KB Output is correct
7 Correct 36 ms 16404 KB Output is correct
8 Correct 301 ms 82672 KB Output is correct
9 Correct 283 ms 82372 KB Output is correct
10 Correct 30 ms 16268 KB Output is correct
11 Correct 286 ms 86400 KB Output is correct
12 Correct 278 ms 86208 KB Output is correct
13 Correct 349 ms 86196 KB Output is correct
14 Correct 37 ms 17012 KB Output is correct
15 Correct 248 ms 85332 KB Output is correct
16 Correct 328 ms 85436 KB Output is correct
17 Correct 291 ms 85840 KB Output is correct
18 Correct 340 ms 85800 KB Output is correct
19 Correct 461 ms 87924 KB Output is correct
20 Correct 421 ms 86848 KB Output is correct
21 Correct 359 ms 85716 KB Output is correct
22 Correct 286 ms 85624 KB Output is correct
23 Correct 328 ms 86008 KB Output is correct
24 Correct 361 ms 86108 KB Output is correct
25 Correct 342 ms 85932 KB Output is correct
26 Correct 381 ms 85072 KB Output is correct
27 Correct 323 ms 85036 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16220 KB Output is correct
2 Correct 35 ms 18780 KB Output is correct
3 Correct 44 ms 19028 KB Output is correct
4 Correct 38 ms 19024 KB Output is correct
5 Correct 49 ms 19036 KB Output is correct
6 Correct 39 ms 18824 KB Output is correct
7 Correct 36 ms 16404 KB Output is correct
8 Correct 301 ms 82672 KB Output is correct
9 Correct 283 ms 82372 KB Output is correct
10 Correct 30 ms 16268 KB Output is correct
11 Correct 286 ms 86400 KB Output is correct
12 Correct 278 ms 86208 KB Output is correct
13 Correct 349 ms 86196 KB Output is correct
14 Correct 37 ms 17012 KB Output is correct
15 Correct 248 ms 85332 KB Output is correct
16 Correct 328 ms 85436 KB Output is correct
17 Correct 291 ms 85840 KB Output is correct
18 Correct 340 ms 85800 KB Output is correct
19 Correct 461 ms 87924 KB Output is correct
20 Correct 421 ms 86848 KB Output is correct
21 Correct 359 ms 85716 KB Output is correct
22 Correct 286 ms 85624 KB Output is correct
23 Correct 328 ms 86008 KB Output is correct
24 Correct 361 ms 86108 KB Output is correct
25 Correct 342 ms 85932 KB Output is correct
26 Correct 381 ms 85072 KB Output is correct
27 Correct 323 ms 85036 KB Output is correct
28 Correct 44 ms 17240 KB Output is correct
29 Correct 408 ms 19836 KB Output is correct
30 Correct 764 ms 20192 KB Output is correct
31 Correct 353 ms 20048 KB Output is correct
32 Correct 283 ms 20204 KB Output is correct
33 Correct 835 ms 20520 KB Output is correct
34 Correct 42 ms 17268 KB Output is correct
35 Correct 1452 ms 90416 KB Output is correct
36 Correct 1157 ms 89860 KB Output is correct
37 Correct 1569 ms 90192 KB Output is correct
38 Correct 31 ms 17052 KB Output is correct
39 Correct 481 ms 88848 KB Output is correct
40 Correct 1483 ms 88960 KB Output is correct
41 Correct 675 ms 88488 KB Output is correct
42 Correct 712 ms 88512 KB Output is correct
43 Correct 39 ms 17104 KB Output is correct
44 Correct 1325 ms 85024 KB Output is correct
45 Correct 573 ms 85008 KB Output is correct
46 Correct 566 ms 85316 KB Output is correct
47 Correct 674 ms 85580 KB Output is correct
48 Execution timed out 3507 ms 86360 KB Time limit exceeded
49 Halted 0 ms 0 KB -