Submission #708948

#	Time	Username	Problem	Language	Result	Execution time	Memory
708948		gokussjz	Valley (BOI19_valley)	C++17	23 / 100	330 ms	52624 KiB

valley

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define all(x)      x.begin(), x.end()
#define pb          push_back
#define sz(x)       (int)(x.size())
#define ll          long long
#define fi          first
#define se          second
#define lbd         lower_bound
#define ubd         upper_bound

template <typename T>
using ordered_set = tree<T, null_type,
      less<T>, rb_tree_tag,
      tree_order_statistics_node_update>;

const int MOD = 1e9 + 7;
const double eps = 1e-10;
const long long INF = 1e18;
const int N = 2e5 + 10;


void solve() {
	int n, s, q, st;
	cin >> n >> s >> q >> st;
	--st;
	vector<vector<pair<int, ll>>> adj(n);
	vector<pair<int, int>> edges(n);
	for (int i = 1; i < n; i++) {
		int u, v, x;
		cin >> u >> v >> x;
		--u, --v;
		adj[u].pb({v, x});
		adj[v].pb({u, x});
		edges[i] = {u, v};
	}
	bool c[n] = {};
	for (int i = 0; i < s; i++) {
		int x;
		cin >> x;
		c[x - 1] = 1;
	}

	vector<vector<int>> par(n, vector<int>(20, -1));
	vector<vector<ll>> d(n, vector<ll>(20, INF));
	vector<ll> depth(n), f(n, INF), dist(n);
	function<void(int, int)> dfs = [&](int u, int p) {
		par[u][0] = p;
		if (c[u]) f[u] = 0;
		for (auto [v, x] : adj[u]) {
			if (v != p) {
				depth[v] = depth[u] + 1;
				dist[v] = dist[u] + x;
				dfs(v, u);
				f[u] = min(f[u], f[v] + x);
			}
		}
		if (f[u] == INF) return;
		for (auto [v, x] : adj[u]) {
			if (v != p) {
				d[v][0] = f[u] - dist[u];
			}
		}
	};
	dfs(st, -1);

	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < n; j++) {
			if (par[j][i - 1] != -1) par[j][i] = par[par[j][i - 1]][i - 1];
		}
	}
	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < n; j++) {
			if (par[j][i - 1] != -1) d[j][i] = min(d[j][i - 1], d[par[j][i - 1]][i - 1]);
		}
	}

	auto lift = [&](int u, int d) {
		for (int i = 0; i < 20; i++) {
			if (((1 << i) & d) && u != -1) u = par[u][i];
		}
		return u;
	};

	auto lca = [&](int u, int v) {
		v = lift(v, depth[v] - depth[u]);
		if (u == v) return u;
		for (int i = 19; i >= 0; --i) {
			if (u != -1 && par[u][i] != par[v][i]) {
				u = par[u][i];
				v = par[v][i];
			}
		}
		return par[u][0];
	};

	while (q--) {
		int idx, u;
		cin >> idx >> u;
		--u;
		auto [a, b] = edges[idx];
		if (depth[a] > depth[b]) swap(a, b);
		if (depth[b] > depth[u] || lca(b, u) != b) {
			cout << "escaped\n";
			continue;
		}
		ll ans = f[u];
		int curr = depth[u] - depth[b];
		for (int i = 0; i < 20; i++) {
			if ((1 << i) & curr) {
				ans = min(ans, dist[u] + d[u][i]);
				u = par[u][i];
			}
		}
		if (ans == INF) cout << "oo\n";
		else cout << ans << '\n';
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int tt = 1;
	//cin >> tt;
	while (tt--) {
		solve();
		cout << '\n';
	}
	return 0;
}

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