oj.uz

Submission #912661

# Submission time Handle Problem Language Result Execution time Memory
912661 2024-01-19T17:24:05 Z MinaRagy06 Inside information (BOI21_servers) C++17
25 / 100
 3500 ms 524288 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 = 18, B = 700;
vector<array<int, 3>> adj[N];
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];
}
int st[N], en[N], sz[N], curt;
array<int, 2> par[N];
bool isanc(int u, int v) {
	return st[u] <= st[v] && en[v] <= en[u];
}
struct sparse {
	array<int, 2> a[2 * N][LOG + 1];
	int n;
	int logs[2 * N];
	void build(int _n) {
		n = _n;
		logs[1] = 0;
		for (int j = 2; j <= n; j++) {
			logs[j] = logs[j >> 1] + 1;
		}
		for (int j = 1; j <= LOG; j++) {
			for (int i = 0; i + (1 << (j - 1)) < n; i++) {
				a[i][j] = min(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
			}
		}
	}
	int query(int u, int v) {
		if (st[u] > st[v]) swap(u, v);
		if (isanc(u, v)) {
			return u;
		}
		int l = en[u], r = st[v];
		int lg = logs[r - l + 1];
		array<int, 2> mn = min(a[l][lg], a[r - (1 << lg) + 1][lg]);
		return mn[1];
	}
} lca;
void dfs(int i, int h, int p, int part) {
	lca.a[curt][0] = {h, i};
	st[i] = curt++;
	sz[i] = 1;
	par[i] = {p, part};
	for (int j = 0; j < SZ(adj[i]); j++) {
		auto [nxt, t, nxtidx] = adj[i][j];
		if (nxt == p) continue;
		dfs(nxt, h + 1, i, t);
		sz[i] += sz[nxt];
		lca.a[curt][0] = {h, i};
		curt++;
	}
	en[i] = curt - 1;
}
vector<array<int, 4>> ask[N];
int ans[2 * N];
void process(int i, int p) {
	for (auto [a, b, t, idx] : ask[i]) {
		int cur = a, lst1 = -1e9;
		bool ok = 1;
		while (cur != i) {
			ok &= lst1 < par[cur][1];
			lst1 = par[cur][1];
			cur = par[cur][0];
		}
		cur = b;
		int lst2 = 1e9;
		while (cur != i) {
			ok &= par[cur][1] < lst2;
			lst2 = par[cur][1];
			cur = par[cur][0];
		}
		ok &= lst1 < lst2;
		if (b != i) {
			ok &= par[b][1] <= t;
		} else if (a != i) {
			ok &= lst1 <= t;
		}
		ans[idx] += ok;
	}
	for (auto [nxt, t, nxtidx] : adj[i]) {
		if (nxt == p) continue;
		process(nxt, i);
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	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, 0, 1, 0);
	lca.build(curt);
	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;
	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];
			int mid = lca.query(a, b);
			ask[mid].push_back({b, a, i, i});
		} else {
			int x = v[i].second[0];
			ans[i] += solve(x, adj[x].size());
			for (auto [a, b, t] : upd) {
				if (isanc(b, x)) {
					ask[b].push_back({x, b, t - 1, i});
				} else if (isanc(a, x)) {
					ask[a].push_back({x, a, t - 1, i});
				} else {
					int mid = lca.query(a, x);
					ask[mid].push_back({x, a, t - 1, i});
				}
			}
		}
	}
	process(1, 1);
	for (int i = 0; i < q; i++) {
		if (v[i].first == 'Q') {
			cout << (ans[i]? "yes\n" : "no\n");
		} else if (v[i].first == 'C') {
			cout << ans[i] << '\n';
		}
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24252 KB Output is correct
2 Correct 45 ms 28052 KB Output is correct
3 Correct 40 ms 28392 KB Output is correct
4 Correct 217 ms 28356 KB Output is correct
5 Correct 373 ms 29124 KB Output is correct
6 Correct 35 ms 27756 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24252 KB Output is correct
2 Correct 45 ms 28052 KB Output is correct
3 Correct 40 ms 28392 KB Output is correct
4 Correct 217 ms 28356 KB Output is correct
5 Correct 373 ms 29124 KB Output is correct
6 Correct 35 ms 27756 KB Output is correct
7 Correct 40 ms 32236 KB Output is correct
8 Correct 1053 ms 383988 KB Output is correct
9 Correct 531 ms 519848 KB Output is correct
10 Execution timed out 3619 ms 462156 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 23748 KB Output is correct
2 Correct 229 ms 79240 KB Output is correct
3 Correct 244 ms 79360 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 23748 KB Output is correct
2 Correct 229 ms 79240 KB Output is correct
3 Correct 244 ms 79360 KB Output is correct
4 Correct 34 ms 30564 KB Output is correct
5 Correct 895 ms 346036 KB Output is correct
6 Runtime error 416 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24444 KB Output is correct
2 Correct 318 ms 87636 KB Output is correct
3 Correct 294 ms 87768 KB Output is correct
4 Execution timed out 3547 ms 86944 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24444 KB Output is correct
2 Correct 318 ms 87636 KB Output is correct
3 Correct 294 ms 87768 KB Output is correct
4 Execution timed out 3547 ms 86944 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23972 KB Output is correct
2 Correct 242 ms 79424 KB Output is correct
3 Correct 312 ms 79636 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23972 KB Output is correct
2 Correct 242 ms 79424 KB Output is correct
3 Correct 312 ms 79636 KB Output is correct
4 Correct 37 ms 29900 KB Output is correct
5 Correct 1430 ms 498332 KB Output is correct
6 Correct 2179 ms 518656 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 24408 KB Output is correct
2 Correct 329 ms 87636 KB Output is correct
3 Correct 309 ms 87420 KB Output is correct
4 Execution timed out 3553 ms 87100 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 24408 KB Output is correct
2 Correct 329 ms 87636 KB Output is correct
3 Correct 309 ms 87420 KB Output is correct
4 Execution timed out 3553 ms 87100 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24248 KB Output is correct
2 Correct 43 ms 28152 KB Output is correct
3 Correct 42 ms 28528 KB Output is correct
4 Correct 236 ms 28404 KB Output is correct
5 Correct 373 ms 29012 KB Output is correct
6 Correct 35 ms 27700 KB Output is correct
7 Correct 29 ms 24640 KB Output is correct
8 Correct 226 ms 79252 KB Output is correct
9 Correct 265 ms 79200 KB Output is correct
10 Correct 32 ms 25172 KB Output is correct
11 Correct 298 ms 87592 KB Output is correct
12 Correct 317 ms 87664 KB Output is correct
13 Execution timed out 3532 ms 86808 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24248 KB Output is correct
2 Correct 43 ms 28152 KB Output is correct
3 Correct 42 ms 28528 KB Output is correct
4 Correct 236 ms 28404 KB Output is correct
5 Correct 373 ms 29012 KB Output is correct
6 Correct 35 ms 27700 KB Output is correct
7 Correct 29 ms 24640 KB Output is correct
8 Correct 226 ms 79252 KB Output is correct
9 Correct 265 ms 79200 KB Output is correct
10 Correct 32 ms 25172 KB Output is correct
11 Correct 298 ms 87592 KB Output is correct
12 Correct 317 ms 87664 KB Output is correct
13 Execution timed out 3532 ms 86808 KB Time limit exceeded
14 Halted 0 ms 0 KB -