Submission #997055

#	Time	Username	Problem	Language	Result	Execution time	Memory
997055		goats_9	Valley (BOI19_valley)	C++17	23 / 100	1116 ms	73772 KiB

valley

/* Author: goats_9 */

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = 1e18;

struct item {
	int idx;
	ll psm;
	ll mn;
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, s, q, e;
	cin >> n >> s >> q >> e;
	e--;
	vector<array<ll, 3>> edges(n);
	vector<vector<array<ll, 2>>> adj(n, vector<array<ll, 2>>());
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		edges[i] = {u, v, w};
	}
	vector<ll> store(n, INF), depth(n, 0);
	vector<vector<item>> par(21, vector<item>(n, {0, 0, INF}));
	while (s--) {
		int x;
		cin >> x;
		x--;
		store[x] = 0;
	}
	function<void(int, int)> dfs = [&] (int u, int p) {
		for (auto [v, w] : adj[u]) {
			if (v == p) continue;
			depth[v] = depth[u] + 1;
			dfs(v, u);
			store[u] = min(store[u], w + store[v]);
		}
		for (auto [v, w] : adj[u]) {
			par[0][v] = {u, w, min(store[v], store[u] + w)};
		}
	};
	auto merge = [&] (item a, item b) -> item {
		item c;
		c.idx = b.idx;
		c.psm = a.psm + b.psm;
		c.mn = min(a.mn, c.psm + store[c.idx]);
		return c;
	};
	dfs(e, -1);
	for (int i = 1; i < 21; i++)
		for (int j = 0; j < n; j++)
			par[i][j] = merge(par[i - 1][j], par[i - 1][par[i - 1][j].idx]);
	while (q--) {
		int i, r;
		cin >> i >> r;
		r--;
		auto &[u, v, _] = edges[i];
		if (depth[u] == depth[v] + 1) swap(u, v);
		int d = depth[r] - depth[v];
		cerr << r << ' ' << u << ' ' << v << ' ' << d << '\n';
		if (d < 0) {
			cout << "escaped\n";
			continue;
		}
		if (d == 0 && r != v) {
			cout << "escaped\n";
			continue;
		}
		int pv = r;
		ll ans = store[r], psm = 0;
		for (int j = 0; j < 21; j++) if (d&(1<<j)) psm += par[j][pv].psm, pv = par[j][pv].idx, ans = min(ans, psm + store[pv]);
		if (pv != v) {
			cout << "escaped\n";
			continue;
		}
		if (ans >= INF) {
			cout << "oo\n";
			continue;
		}
		cout << ans << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41