oj.uz

Submission #911133

# Submission time Handle Problem Language Result Execution time Memory
911133 2024-01-18T13:30:15 Z MinaRagy06 Inside information (BOI21_servers) C++17
30 / 100
 1298 ms 87960 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define SZ(x) (int) x.size()

const int N = 120'005, LOG = 17, 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:83:7: warning: unused variable 'S' [-Wunused-variable]
   83 |  auto S = chrono::steady_clock::now().time_since_epoch().count();
      |       ^
servers.cpp:116:5: warning: unused variable 's' [-Wunused-variable]
  116 |  ll s = 0;
      |     ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16468 KB Output is correct
2 Correct 36 ms 19496 KB Output is correct
3 Correct 44 ms 19604 KB Output is correct
4 Correct 36 ms 19548 KB Output is correct
5 Correct 34 ms 19660 KB Output is correct
6 Correct 44 ms 19572 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16468 KB Output is correct
2 Correct 36 ms 19496 KB Output is correct
3 Correct 44 ms 19604 KB Output is correct
4 Correct 36 ms 19548 KB Output is correct
5 Correct 34 ms 19660 KB Output is correct
6 Correct 44 ms 19572 KB Output is correct
7 Correct 52 ms 16416 KB Output is correct
8 Correct 356 ms 19280 KB Output is correct
9 Correct 727 ms 19456 KB Output is correct
10 Correct 362 ms 19280 KB Output is correct
11 Correct 319 ms 19280 KB Output is correct
12 Correct 694 ms 19676 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16464 KB Output is correct
2 Correct 293 ms 82560 KB Output is correct
3 Correct 289 ms 82420 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16464 KB Output is correct
2 Correct 293 ms 82560 KB Output is correct
3 Correct 289 ms 82420 KB Output is correct
4 Correct 38 ms 16472 KB Output is correct
5 Correct 1280 ms 87960 KB Output is correct
6 Correct 954 ms 87556 KB Output is correct
7 Correct 1298 ms 87496 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16468 KB Output is correct
2 Correct 263 ms 86864 KB Output is correct
3 Correct 258 ms 86868 KB Output is correct
4 Incorrect 303 ms 86608 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16468 KB Output is correct
2 Correct 263 ms 86864 KB Output is correct
3 Correct 258 ms 86868 KB Output is correct
4 Incorrect 303 ms 86608 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 27 ms 16472 KB Output is correct
2 Correct 224 ms 83028 KB Output is correct
3 Correct 270 ms 82984 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16472 KB Output is correct
2 Correct 224 ms 83028 KB Output is correct
3 Correct 270 ms 82984 KB Output is correct
4 Correct 35 ms 16292 KB Output is correct
5 Correct 1086 ms 82716 KB Output is correct
6 Correct 531 ms 82572 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16476 KB Output is correct
2 Correct 252 ms 86956 KB Output is correct
3 Correct 279 ms 86712 KB Output is correct
4 Incorrect 289 ms 86612 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 16476 KB Output is correct
2 Correct 252 ms 86956 KB Output is correct
3 Correct 279 ms 86712 KB Output is correct
4 Incorrect 289 ms 86612 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16472 KB Output is correct
2 Correct 36 ms 19604 KB Output is correct
3 Correct 39 ms 19540 KB Output is correct
4 Correct 38 ms 19488 KB Output is correct
5 Correct 39 ms 19548 KB Output is correct
6 Correct 39 ms 19536 KB Output is correct
7 Correct 30 ms 16464 KB Output is correct
8 Correct 270 ms 82112 KB Output is correct
9 Correct 284 ms 82176 KB Output is correct
10 Correct 27 ms 16476 KB Output is correct
11 Correct 276 ms 86272 KB Output is correct
12 Correct 257 ms 86356 KB Output is correct
13 Incorrect 290 ms 86332 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16472 KB Output is correct
2 Correct 36 ms 19604 KB Output is correct
3 Correct 39 ms 19540 KB Output is correct
4 Correct 38 ms 19488 KB Output is correct
5 Correct 39 ms 19548 KB Output is correct
6 Correct 39 ms 19536 KB Output is correct
7 Correct 30 ms 16464 KB Output is correct
8 Correct 270 ms 82112 KB Output is correct
9 Correct 284 ms 82176 KB Output is correct
10 Correct 27 ms 16476 KB Output is correct
11 Correct 276 ms 86272 KB Output is correct
12 Correct 257 ms 86356 KB Output is correct
13 Incorrect 290 ms 86332 KB Output isn't correct
14 Halted 0 ms 0 KB -