Submission #380524

#	Time	Username	Problem	Language	Result	Execution time	Memory
380524		badont	Valley (BOI19_valley)	C++14	100 / 100	320 ms	61452 KiB

valley

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<LL,LL> pii;
typedef pair<LL,pii> ppi;
typedef pair<pii,pii> ppp;
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {cout << "["; F0R(i, v.size()) {if (i) cout << ", "; cout << v[i];} return cout << "]";}

//var 
const LL INF = 1e16;
LL T, n, s, q, st, t1, t2, t3, cc;
vector<pii> e[100005];
LL bl[100005][25], dp[100005][25], dep[100005], tin[100005], tout[100005], shop[100005], mnshopsub[100005];
pii ed[100005];

void dfs(LL g, LL p, LL d){
	dep[g] = d;
	bl[g][0] = p;

	cc++; tin[g] = cc;
	if(shop[g]) mnshopsub[g] = 0;

	FOR(i, 17)
		bl[g][i] = bl[bl[g][i-1]][i-1];

	for(auto u : e[g]){
		if(u.s == p) continue;
		dfs(u.s, g, d + u.f);
		mnshopsub[g] = min(mnshopsub[g], mnshopsub[u.s] + u.f);
	}

	cc++; tout[g] = cc; 
}

void solve(){
	cin >> n >> s >> q >> st;
	FOR(i, n) mnshopsub[i] = INF;
	FOR(i, n-1){
		cin >> t1 >> t2 >> t3;
		e[t1].pb({t3, t2});
		e[t2].pb({t3, t1});
		ed[i] = mp(t1, t2);
	}

	FOR(i, s){
		cin >> t1;
		shop[t1] = 1;
	}

	dfs(st, 0, 1);
	FOR(i, n) F0R(j, 18) dp[i][j] = INF;

	FOR(i, n) dp[i][0] = mnshopsub[i];
	FOR(j, 17) FOR(i, n){
		dp[i][j] = min(dp[i][j], min(
			dp[i][j-1], dp[bl[i][j-1]][j-1] - dep[bl[i][j-1]] + dep[i]
		));
	}

	FOR(i, n-1){
		if(dep[ed[i].f] > dep[ed[i].s])
			swap(ed[i].f, ed[i].s);
	}

	while(q--){
		cin >> t1 >> t2;
		LL tt = t1;
		t1 = ed[t1].s;
		if(tin[t2] < tin[t1] || tout[t2] > tout[t1]){
			cout << "escaped\n";
			continue;
		} 

		t1 = ed[tt].f;
		
		LL res = INF, ad = 0;
		for(int j = 17; j>=0; j--){
			if(dep[bl[t2][j]] < dep[t1]) continue;

			res = min(res, dp[t2][j] + ad);
			ad += dep[t2] - dep[bl[t2][j]];
			t2 = bl[t2][j];
		}

		if(res >= INF){
			cout << "oo" << '\n';
			continue;
		}

		cout << res << '\n';
	}
}

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

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

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