Submission #954712

#	Time	Username	Problem	Language	Result	Execution time	Memory
954712		Angus_Yeung	Valley (BOI19_valley)	C++17	100 / 100	207 ms	53880 KiB

valley

#include <bits/stdc++.h>
#define len first
#define node second
#define pii pair<ll, ll>
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1e15;
using namespace std;

struct edge {
	ll u, v, w, id;
};

ll n, s, q, E, x, y, ans, tmp;
bool c[100010];
ll t, up[20][100010], tin[100010], tout[100010], dep[100010];
ll dp[100010], val[20][100010];
edge e[100010];
vector<pii> a[100010];

void dfs(ll x, ll p, ll dis) {
	tin[x] = ++t;
	dp[x] = (c[x]? 0: INF);
	dep[x] = dis;
	up[0][x] = p;
	for (int i = 1; i <= 18; i++) up[i][x] = up[i-1][up[i-1][x]];
	for (auto i: a[x]) {
		if (i.node == p) continue;
		dfs(i.node, x, dis+i.len);
		dp[x] = min(dp[x], dp[i.node]+i.len);
	}
	tout[x] = ++t;
}

void dfs2(ll x, ll p) {
	val[0][x] = dp[x]-dep[x];
	for (int i = 1; i <= 18; i++) val[i][x] = min(val[i-1][x], val[i-1][up[i-1][x]]);
	for (auto i: a[x]) {
		if (i.node == p) continue;
		dfs2(i.node, x);
	}
}

bool isa(ll x, ll y) {
	return tin[x] <= tin[y] && tout[y] <= tout[x];
}

int main() {
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> s >> q >> E;
	for (int i = 1; i < n; i++) {
		cin >> e[i].u >> e[i].v >> e[i].w;
		a[e[i].u].push_back({e[i].w, e[i].v});
		a[e[i].v].push_back({e[i].w, e[i].u});
		e[i].id = i;
	}
	
	for (int i = 1; i <= n; i++) c[i] = 0;
	for (int i = 1; i <= s; i++) {
		cin >> x;
		c[x] = 1;
	}
	
	t = 0;
	dfs(E, E, 0);
	dfs2(E, E);
	
	while (q--) {
		cin >> x >> y;
		if (isa(e[x].v, e[x].u)) swap(e[x].u, e[x].v);
		if (isa(e[x].v, y)) {
			if (dp[e[x].v] == INF) cout << "oo\n";
			else if (e[x].v == y) cout << dp[y] << "\n";
			else {
				ans = INF; tmp = y;
				for (int i = 18; i >= 0; i--) {
					if (!isa(up[i][y], e[x].v)) {
						ans = min(ans, val[i][y]);
						y = up[i][y];
					}
				}
				ans = min(ans, val[1][y]);
				cout << ans+dep[tmp] << "\n";
			}
		}
		else cout << "escaped\n";
	}
	
	return 0;
}

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