Submission #696092

#	Time	Username	Problem	Language	Result	Execution time	Memory
696092		Kahou	Valley (BOI19_valley)	C++14	100 / 100	226 ms	50728 KiB

valley

/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll inf = 1e18;
const int N = 1e5 + 50, LG = 20;
ll n, s, q, e, par[LG][N], sp[LG][N], dp[N], h[N], dis[N];
pll E[N];
vector<pll> adj[N];

void dfs(int u, int p) {
	par[0][u] = p;
	for (pll x:adj[u]) {
		int v = x.F, w = x.S;
		if (v == p) continue;
		dis[v] = dis[u]+w;
		h[v] = h[u] + 1;
		dfs(v, u);
		dp[u] = min(dp[u], dp[v]+w);
	}
	sp[0][u] = dp[u]-dis[u];
}

pll Par(int u, int x) {
	ll out = inf;
	for (int k = LG-1; k >= 0; k--) {
		if (x>>k&1) {
			out = min(out, sp[k][u]);
			u = par[k][u];
		}
	}
	out = min(out, sp[0][u]);
	return {u, out};
}
void solve() {
	cin >> n >> s >> q >> e;
	for (int i = 1; i <= n-1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		E[i] = {u, v};
	}
	for (int u = 1; u <= n; u++) {
		dp[u] = inf;
	}
	for (int i = 1; i <= s; i++) {
		int u;
		cin >> u;
		dp[u] = 0;
	}
	dfs(e, 0);
	for (int i = 1; i <= n-1; i++) {
		if (h[E[i].F] < h[E[i].S]) swap(E[i].F, E[i].S);
	}
	for (int k = 1; k < LG; k++) {
		for (int u = 1; u <= n; u++) {
			par[k][u] = par[k-1][par[k-1][u]];
			sp[k][u] = min(sp[k-1][u],sp[k-1][par[k-1][u]]);
		}
	}
	
	while (q--) {
		int u, id;
		cin >> id >> u;
		pll out = Par(u, h[u]-h[E[id].F]);
		if (out.F != E[id].F) {
			cout << "escaped" << endl;
		}
		else {
			ll ans = out.S + dis[u];
			if (ans >= inf) cout << "oo" << endl;
			else cout << ans << endl;
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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