oj.uz

Submission #911134

# Submission time Handle Problem Language Result Execution time Memory
911134 2024-01-18T13:30:40 Z MinaRagy06 Inside information (BOI21_servers) C++17
30 / 100
 1329 ms 85580 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, 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 28 ms 15440 KB Output is correct
2 Correct 38 ms 18000 KB Output is correct
3 Correct 38 ms 18240 KB Output is correct
4 Correct 33 ms 18256 KB Output is correct
5 Correct 33 ms 18260 KB Output is correct
6 Correct 36 ms 18240 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15440 KB Output is correct
2 Correct 38 ms 18000 KB Output is correct
3 Correct 38 ms 18240 KB Output is correct
4 Correct 33 ms 18256 KB Output is correct
5 Correct 33 ms 18260 KB Output is correct
6 Correct 36 ms 18240 KB Output is correct
7 Correct 38 ms 15452 KB Output is correct
8 Correct 329 ms 18212 KB Output is correct
9 Correct 688 ms 18572 KB Output is correct
10 Correct 313 ms 18004 KB Output is correct
11 Correct 240 ms 18180 KB Output is correct
12 Correct 624 ms 18684 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15444 KB Output is correct
2 Correct 262 ms 79604 KB Output is correct
3 Correct 282 ms 79732 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15444 KB Output is correct
2 Correct 262 ms 79604 KB Output is correct
3 Correct 282 ms 79732 KB Output is correct
4 Correct 39 ms 15452 KB Output is correct
5 Correct 854 ms 85312 KB Output is correct
6 Correct 880 ms 85580 KB Output is correct
7 Correct 1329 ms 85548 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15588 KB Output is correct
2 Correct 257 ms 83540 KB Output is correct
3 Correct 239 ms 83572 KB Output is correct
4 Incorrect 294 ms 83488 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15588 KB Output is correct
2 Correct 257 ms 83540 KB Output is correct
3 Correct 239 ms 83572 KB Output is correct
4 Incorrect 294 ms 83488 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 15444 KB Output is correct
2 Correct 226 ms 79916 KB Output is correct
3 Correct 254 ms 79700 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15444 KB Output is correct
2 Correct 226 ms 79916 KB Output is correct
3 Correct 254 ms 79700 KB Output is correct
4 Correct 35 ms 15440 KB Output is correct
5 Correct 1055 ms 80240 KB Output is correct
6 Correct 530 ms 79700 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15480 KB Output is correct
2 Correct 242 ms 83540 KB Output is correct
3 Correct 262 ms 83736 KB Output is correct
4 Incorrect 275 ms 83540 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 15480 KB Output is correct
2 Correct 242 ms 83540 KB Output is correct
3 Correct 262 ms 83736 KB Output is correct
4 Incorrect 275 ms 83540 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 15444 KB Output is correct
2 Correct 33 ms 18000 KB Output is correct
3 Correct 36 ms 18176 KB Output is correct
4 Correct 34 ms 18268 KB Output is correct
5 Correct 32 ms 18264 KB Output is correct
6 Correct 37 ms 18260 KB Output is correct
7 Correct 30 ms 15440 KB Output is correct
8 Correct 254 ms 79620 KB Output is correct
9 Correct 258 ms 79788 KB Output is correct
10 Correct 25 ms 15444 KB Output is correct
11 Correct 233 ms 83536 KB Output is correct
12 Correct 271 ms 83544 KB Output is correct
13 Incorrect 272 ms 83304 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 15444 KB Output is correct
2 Correct 33 ms 18000 KB Output is correct
3 Correct 36 ms 18176 KB Output is correct
4 Correct 34 ms 18268 KB Output is correct
5 Correct 32 ms 18264 KB Output is correct
6 Correct 37 ms 18260 KB Output is correct
7 Correct 30 ms 15440 KB Output is correct
8 Correct 254 ms 79620 KB Output is correct
9 Correct 258 ms 79788 KB Output is correct
10 Correct 25 ms 15444 KB Output is correct
11 Correct 233 ms 83536 KB Output is correct
12 Correct 271 ms 83544 KB Output is correct
13 Incorrect 272 ms 83304 KB Output isn't correct
14 Halted 0 ms 0 KB -