Submission #473704

#	Time	Username	Problem	Language	Result	Execution time	Memory
473704		disastah	Valley (BOI19_valley)	C++17	100 / 100	236 ms	42692 KiB

valley

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ar array
using namespace std;
typedef long double ld;
typedef long long ll;
const int inf=1e9+1e8;
const ll linf=4e18+18;
const int N=1e5;

int n, shops, q, st;
ar<int,3> e[N];
vector<ar<int,2>> g[N];
bool shop[N];
int par[N], lvl[N], tin[N], tout[N], timer=0;
ll h[N], trshop[N];
void dfs(int v, int p=-1) {
	tin[v]=timer++;
	trshop[v]=linf;
	if (shop[v]) trshop[v]=0LL;
	for (auto &[u,c] : g[v]) {
		if (u!=p) {
			par[u]=v;
			lvl[u]=lvl[v]+1;
			h[u]=h[v]+c;
			dfs(u,v);
			trshop[v]=min(trshop[v],min(linf,trshop[u]+c));
		}
	}
	tout[v]=timer++;
}
int bup[N][20]; ll bshop[N][20];
void solve() {
	cin >> n >> shops >> q >> st; --st;
	for (int i=0; i<n-1; ++i) {
		int u, v, c; cin >> u >> v >> c; --u, --v;
		e[i]={u,v,c};
		g[u].push_back({v,c});
		g[v].push_back({u,c});
	}
	for (int i=0; i<shops; ++i) {
		int x; cin >> x; --x;
		shop[x]=1;
	}
	par[st]=st, h[st]=0LL;
	dfs(st);
	for (int d=0; d<20; ++d) {
		for (int i=0; i<n; ++i) {
			if (!d) {
				bup[i][d]=par[i];
				bshop[i][d]=h[i]-h[par[i]]+trshop[par[i]];
			}
			else {
				bup[i][d]=bup[bup[i][d-1]][d-1];
				bshop[i][d]=min(bshop[i][d-1],bshop[bup[i][d-1]][d-1]+h[i]-h[bup[i][d-1]]);
			}
		}
	}
	int ind, x;
	while(q--) {
		cin >> ind >> x; --ind, --x;
		auto &[v1,v2,c]=e[ind];
		if (tin[v2]<tin[v1]&&tout[v2]>tout[v1]) swap(v1,v2);
		if (tin[v2]<=tin[x]&&tout[v2]>=tout[x]) {
			ll ans=trshop[x];
			int v=x, dh=lvl[x]-lvl[v2];
			for (int i=0; i<20; ++i) {
				if ((dh>>i)&1) {
					ans=min(ans,h[x]-h[v]+bshop[v][i]);
					v=bup[v][i];
				}
			}
			if (ans<linf) cout << ans << "\n";
			else cout << "oo\n";
		}
		else cout << "escaped\n";
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
#ifdef disastah
	cout << "Output\n\n";
#endif
	int tt=1;
//	cin >> tt;
	while (tt--) {
		solve();
		cout << "\n";
	}
}

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