oj.uz

Submission #910123

# Submission time Handle Problem Language Result Execution time Memory
910123 2024-01-17T23:26:38 Z MinaRagy06 Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 93204 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define SZ(x) (int) x.size()

const int N = 120'005;
vector<array<int, 3>> adj[N];
//0: increasing, 1: decreasing, {ancestor, last weight}
array<int, 3> bl[2][18][N];
int st[N], en[N], curt;
void dfs(int i, int par, int part) {
	bl[0][0][i] = {par, part, part};
	bl[1][0][i] = {par, part, part};
	for (int j = 1; j < 18; j++) {
		bl[0][j][i] = bl[0][j - 1][i];
		auto [lst, lstt, mx] = bl[0][j][i];
		if (lstt <= bl[0][0][lst][1]) {
			bl[0][j][i] = bl[0][j - 1][lst];
			bl[0][j][i][2] = max(bl[0][j][i][2], mx);
		}
	}
	for (int j = 1; j < 18; j++) {
		bl[1][j][i] = bl[1][j - 1][i];
		auto [lst, lstt, mx] = bl[1][j][i];
		if (lstt >= bl[1][0][lst][1]) {
			bl[1][j][i] = bl[1][j - 1][lst];
			bl[1][j][i][2] = max(bl[1][j][i][2], mx);
		}
	}
	st[i] = curt++;
	for (auto [nxt, t, nxtidx] : adj[i]) {
		if (nxt == par) continue;
		dfs(nxt, i, t);
	}
	en[i] = curt;
}
bool lca(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[t][17][a][0];
	if (!lca(high, b)) {
		return {int(1e9), 0};
	}
	if (a == high || lca(a, b)) {
		return {int(-1e9), (t == 1? 1 : -1) * int(1e9)};
	}
	for (int j = 17; j >= 0; j--) {
		if (!lca(bl[t][j][a][0], b) && !lca(bl[t][j][a][0], high)) {
			mx = max(mx, bl[t][j][a][2]);
			a = bl[t][j][a][0];
		}
	}
	return {max(mx, bl[t][0][a][2]), bl[t][0][a][1]};
}
vector<array<int, 3>> curadj[N];
vector<int> dp[N];
int solve(int i, int par) {
	if (~dp[i][par]) return dp[i][par];
	int prv = -1;
	if (par < SZ(curadj[i])) prv = adj[i][par][1];
	dp[i][par] = 1;
	for (int j = 0; j < SZ(curadj[i]); j++) {
		auto [nxt, t, nxtidx] = curadj[i][j];
		if (j == par || prv >= t) continue;
		dp[i][par] += solve(nxt, nxtidx);
	}
	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 = 400;
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);
	}
	auto recalc = [&] () {
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= SZ(adj[i]); j++) {
				dp[i][j] = -1;
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= SZ(adj[i]); j++) {
				solve(i, j);
			}
		}
	};
	vector<array<int, 3>> upd;
	recalc();
	ll s = 0;
	for (int i = 0; i < q; i++) {
		if (upd.size() == B) {
			for (auto [a, b, t] : upd) {
				int x = curadj[b].size(), y = curadj[a].size();
				curadj[a].push_back({b, t, x});
				curadj[b].push_back({a, t, y});
			}
			upd.clear();
			recalc();
		}
		if (v[i].first == 'S') {
			int a = v[i].second[0], b = v[i].second[1];
			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
// 			cout << i << endl;
			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 = dp[x][adj[x].size()];
			for (auto [a, b, t] : upd) {
				ans += checkpath(x, b, t - 1, 0) || checkpath(x, a, t - 1, 0);
			}
#ifdef MINA
// 			cout << i << endl;
			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';
#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:126:5: warning: unused variable 's' [-Wunused-variable]
  126 |  ll s = 0;
      |     ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 68692 KB Output is correct
2 Correct 46 ms 68944 KB Output is correct
3 Correct 72 ms 69200 KB Output is correct
4 Correct 47 ms 69200 KB Output is correct
5 Correct 44 ms 69228 KB Output is correct
6 Correct 353 ms 69064 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 68692 KB Output is correct
2 Correct 46 ms 68944 KB Output is correct
3 Correct 72 ms 69200 KB Output is correct
4 Correct 47 ms 69200 KB Output is correct
5 Correct 44 ms 69228 KB Output is correct
6 Correct 353 ms 69064 KB Output is correct
7 Correct 57 ms 68432 KB Output is correct
8 Correct 364 ms 69100 KB Output is correct
9 Correct 902 ms 69284 KB Output is correct
10 Correct 428 ms 69164 KB Output is correct
11 Correct 536 ms 69140 KB Output is correct
12 Correct 1593 ms 69564 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 68432 KB Output is correct
2 Execution timed out 3575 ms 85076 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 68432 KB Output is correct
2 Execution timed out 3575 ms 85076 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 68440 KB Output is correct
2 Execution timed out 3508 ms 92792 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 68440 KB Output is correct
2 Execution timed out 3508 ms 92792 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 68332 KB Output is correct
2 Correct 1887 ms 91012 KB Output is correct
3 Execution timed out 3524 ms 88752 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 68332 KB Output is correct
2 Correct 1887 ms 91012 KB Output is correct
3 Execution timed out 3524 ms 88752 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 68436 KB Output is correct
2 Execution timed out 3548 ms 93204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 68436 KB Output is correct
2 Execution timed out 3548 ms 93204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68440 KB Output is correct
2 Correct 51 ms 68900 KB Output is correct
3 Correct 74 ms 69204 KB Output is correct
4 Correct 51 ms 69200 KB Output is correct
5 Correct 45 ms 69204 KB Output is correct
6 Correct 340 ms 69200 KB Output is correct
7 Correct 43 ms 68436 KB Output is correct
8 Execution timed out 3533 ms 85264 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68440 KB Output is correct
2 Correct 51 ms 68900 KB Output is correct
3 Correct 74 ms 69204 KB Output is correct
4 Correct 51 ms 69200 KB Output is correct
5 Correct 45 ms 69204 KB Output is correct
6 Correct 340 ms 69200 KB Output is correct
7 Correct 43 ms 68436 KB Output is correct
8 Execution timed out 3533 ms 85264 KB Time limit exceeded
9 Halted 0 ms 0 KB -