Submission #933677

#	Time	Username	Problem	Language	Result	Execution time	Memory
933677		oblantis	Valley (BOI19_valley)	C++17	100 / 100	180 ms	44488 KiB

valley

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll inf = 1e15;
const int mod = 1e9+7;
const int maxn = 1e5 + 1;
vt<pii> g[maxn];
bool wt[maxn];
int n, s, q, e;
pair<int, ll> up[maxn][18];
ll p[maxn], dp[maxn], mi[maxn];
ll dfs(int v){
	up[v][0].ss = inf;
	mi[v] = inf;
	if(wt[v])mi[v] = 0;
	for(auto i : g[v]){
		if(up[i.ff][0].ff)continue;
		up[i.ff][0].ff = v;
		dp[i.ff] = dp[v] + 1;
		p[i.ff] = p[v] + i.ss;
		mi[v] = min(mi[v], dfs(i.ff) + i.ss);
	}
	if(mi[v] != inf)mi[v] -= p[v];
	for(auto i : g[v]){
		if(up[v][0].ff == i.ff)continue;
		up[i.ff][0].ss = mi[v];
	}
	if(mi[v] != inf)return mi[v] + p[v];
	return inf;
}
void solve() {
	cin >> n >> s >> q >> e;
	int u[n], v[n], d[n];
	for(int i = 1; i < n; i++){
		cin >> u[i] >> v[i] >> d[i];
		g[u[i]].pb({v[i], d[i]});
		g[v[i]].pb({u[i], d[i]});
	}
	for(int i = 0, x; i < s; i++){
		cin >> x;
		wt[x] = 1;
	}
	up[e][0].ff = e;
	dfs(e);
	for(int i = 1; i < 18; i++){
		for(int j = 1; j <= n; j++)up[j][i] = {up[up[j][i - 1].ff][i - 1].ff, min(up[j][i - 1].ss, up[up[j][i - 1].ff][i - 1].ss)};
	}
	for(int i = 1; i < n; i++){
		if(dp[u[i]] > dp[v[i]])swap(u[i], v[i]);
	}
	for(int i = 0; i < q; i++){
		int bl, we;
		cin >> bl >> we;
		int x = dp[we] - dp[v[bl]];
		ll ms = mi[we], out = p[we];
		if(x < 0){
			cout << "escaped\n";
			continue;
		}
		for(int o = 0; o < 18; o++){
			if(x & 1){
				ms = min(ms, up[we][o].ss);
				we = up[we][o].ff;
			}
			x >>= 1;
		}
		if(we != v[bl]){
			cout << "escaped\n";
			continue;
		}
		if(ms == inf)cout << "oo\n";
		else cout << out + ms << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

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