oj.uz

Submission #910175

# Submission time Handle Problem Language Result Execution time Memory
910175 2024-01-18T01:02:12 Z MinaRagy06 Inside information (BOI21_servers) C++17
30 / 100
 1504 ms 85728 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 = 17;
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 = 350;
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 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
			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
			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 27 ms 15444 KB Output is correct
2 Correct 31 ms 18008 KB Output is correct
3 Correct 36 ms 18260 KB Output is correct
4 Correct 44 ms 18184 KB Output is correct
5 Correct 31 ms 18264 KB Output is correct
6 Correct 38 ms 18268 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15444 KB Output is correct
2 Correct 31 ms 18008 KB Output is correct
3 Correct 36 ms 18260 KB Output is correct
4 Correct 44 ms 18184 KB Output is correct
5 Correct 31 ms 18264 KB Output is correct
6 Correct 38 ms 18268 KB Output is correct
7 Correct 38 ms 15476 KB Output is correct
8 Correct 179 ms 18332 KB Output is correct
9 Correct 354 ms 18260 KB Output is correct
10 Correct 167 ms 18208 KB Output is correct
11 Correct 93 ms 18260 KB Output is correct
12 Correct 278 ms 18408 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15468 KB Output is correct
2 Correct 353 ms 79948 KB Output is correct
3 Correct 345 ms 79620 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15468 KB Output is correct
2 Correct 353 ms 79948 KB Output is correct
3 Correct 345 ms 79620 KB Output is correct
4 Correct 37 ms 15448 KB Output is correct
5 Correct 1129 ms 85588 KB Output is correct
6 Correct 1186 ms 85728 KB Output is correct
7 Correct 1504 ms 85388 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15452 KB Output is correct
2 Correct 319 ms 83528 KB Output is correct
3 Correct 327 ms 83520 KB Output is correct
4 Incorrect 377 ms 83424 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15452 KB Output is correct
2 Correct 319 ms 83528 KB Output is correct
3 Correct 327 ms 83520 KB Output is correct
4 Incorrect 377 ms 83424 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15448 KB Output is correct
2 Correct 297 ms 79516 KB Output is correct
3 Correct 356 ms 79640 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15448 KB Output is correct
2 Correct 297 ms 79516 KB Output is correct
3 Correct 356 ms 79640 KB Output is correct
4 Correct 34 ms 15408 KB Output is correct
5 Correct 964 ms 79820 KB Output is correct
6 Correct 486 ms 80168 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15412 KB Output is correct
2 Correct 323 ms 83500 KB Output is correct
3 Correct 334 ms 83460 KB Output is correct
4 Incorrect 360 ms 83436 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15412 KB Output is correct
2 Correct 323 ms 83500 KB Output is correct
3 Correct 334 ms 83460 KB Output is correct
4 Incorrect 360 ms 83436 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15440 KB Output is correct
2 Correct 32 ms 18012 KB Output is correct
3 Correct 36 ms 18260 KB Output is correct
4 Correct 36 ms 18240 KB Output is correct
5 Correct 32 ms 18208 KB Output is correct
6 Correct 37 ms 18108 KB Output is correct
7 Correct 34 ms 15532 KB Output is correct
8 Correct 357 ms 79784 KB Output is correct
9 Correct 341 ms 79992 KB Output is correct
10 Correct 24 ms 15452 KB Output is correct
11 Correct 330 ms 83448 KB Output is correct
12 Correct 346 ms 83772 KB Output is correct
13 Incorrect 347 ms 83284 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15440 KB Output is correct
2 Correct 32 ms 18012 KB Output is correct
3 Correct 36 ms 18260 KB Output is correct
4 Correct 36 ms 18240 KB Output is correct
5 Correct 32 ms 18208 KB Output is correct
6 Correct 37 ms 18108 KB Output is correct
7 Correct 34 ms 15532 KB Output is correct
8 Correct 357 ms 79784 KB Output is correct
9 Correct 341 ms 79992 KB Output is correct
10 Correct 24 ms 15452 KB Output is correct
11 Correct 330 ms 83448 KB Output is correct
12 Correct 346 ms 83772 KB Output is correct
13 Incorrect 347 ms 83284 KB Output isn't correct
14 Halted 0 ms 0 KB -