oj.uz

Submission #910173

# Submission time Handle Problem Language Result Execution time Memory
910173 2024-01-18T01:01:02 Z MinaRagy06 Inside information (BOI21_servers) C++17
30 / 100
 1471 ms 85868 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 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 27 ms 15448 KB Output is correct
2 Correct 32 ms 18000 KB Output is correct
3 Correct 35 ms 18268 KB Output is correct
4 Correct 32 ms 18268 KB Output is correct
5 Correct 30 ms 18268 KB Output is correct
6 Correct 37 ms 18252 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15448 KB Output is correct
2 Correct 32 ms 18000 KB Output is correct
3 Correct 35 ms 18268 KB Output is correct
4 Correct 32 ms 18268 KB Output is correct
5 Correct 30 ms 18268 KB Output is correct
6 Correct 37 ms 18252 KB Output is correct
7 Correct 37 ms 15600 KB Output is correct
8 Correct 172 ms 17952 KB Output is correct
9 Correct 333 ms 18244 KB Output is correct
10 Correct 171 ms 18208 KB Output is correct
11 Correct 107 ms 18276 KB Output is correct
12 Correct 222 ms 18516 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15440 KB Output is correct
2 Correct 330 ms 79632 KB Output is correct
3 Correct 321 ms 79620 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15440 KB Output is correct
2 Correct 330 ms 79632 KB Output is correct
3 Correct 321 ms 79620 KB Output is correct
4 Correct 39 ms 15444 KB Output is correct
5 Correct 1183 ms 85172 KB Output is correct
6 Correct 1195 ms 85868 KB Output is correct
7 Correct 1471 ms 85444 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15456 KB Output is correct
2 Correct 304 ms 83436 KB Output is correct
3 Correct 300 ms 83540 KB Output is correct
4 Incorrect 353 ms 83504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15456 KB Output is correct
2 Correct 304 ms 83436 KB Output is correct
3 Correct 300 ms 83540 KB Output is correct
4 Incorrect 353 ms 83504 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 25 ms 15452 KB Output is correct
2 Correct 286 ms 79556 KB Output is correct
3 Correct 347 ms 79744 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15452 KB Output is correct
2 Correct 286 ms 79556 KB Output is correct
3 Correct 347 ms 79744 KB Output is correct
4 Correct 35 ms 15440 KB Output is correct
5 Correct 992 ms 79732 KB Output is correct
6 Correct 484 ms 80128 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15440 KB Output is correct
2 Correct 314 ms 83428 KB Output is correct
3 Correct 322 ms 83692 KB Output is correct
4 Incorrect 335 ms 83668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15440 KB Output is correct
2 Correct 314 ms 83428 KB Output is correct
3 Correct 322 ms 83692 KB Output is correct
4 Incorrect 335 ms 83668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15452 KB Output is correct
2 Correct 32 ms 18012 KB Output is correct
3 Correct 46 ms 18160 KB Output is correct
4 Correct 34 ms 18068 KB Output is correct
5 Correct 31 ms 18256 KB Output is correct
6 Correct 36 ms 18256 KB Output is correct
7 Correct 35 ms 15452 KB Output is correct
8 Correct 315 ms 79772 KB Output is correct
9 Correct 329 ms 79728 KB Output is correct
10 Correct 24 ms 15452 KB Output is correct
11 Correct 329 ms 83508 KB Output is correct
12 Correct 323 ms 83820 KB Output is correct
13 Incorrect 383 ms 83464 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15452 KB Output is correct
2 Correct 32 ms 18012 KB Output is correct
3 Correct 46 ms 18160 KB Output is correct
4 Correct 34 ms 18068 KB Output is correct
5 Correct 31 ms 18256 KB Output is correct
6 Correct 36 ms 18256 KB Output is correct
7 Correct 35 ms 15452 KB Output is correct
8 Correct 315 ms 79772 KB Output is correct
9 Correct 329 ms 79728 KB Output is correct
10 Correct 24 ms 15452 KB Output is correct
11 Correct 329 ms 83508 KB Output is correct
12 Correct 323 ms 83820 KB Output is correct
13 Incorrect 383 ms 83464 KB Output isn't correct
14 Halted 0 ms 0 KB -