Submission #705625

#	Time	Username	Problem	Language	Result	Execution time	Memory
705625		bane	Valley (BOI19_valley)	C++17	100 / 100	270 ms	59576 KiB

valley

/*
 * prep: 4.3
 */

#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define ll long long 
using i64 = long long;
#ifdef LOCAL
    #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
    #define eprintf(...) 42
#endif
int N = (int)1e5 + 1;
int n,s,q,e;
int t  = 0;
ll inf = (ll)1e15;
vector<i64> in(N), out(N), shop(N), x(N, inf), dp(N), d(N);
vector<pair<int, int>> id(N);
vector<vector<pair<int, int>>> adj(N);
vector<vector<i64>> up(N, vector<i64>(20)), dp2(N, vector<i64>(20));
void DepthFirstSearch(int u, int p){
	up[u][0] = p;
	x[u]=inf;
	in[u]=++t;
    if (shop[u]) {
        x[u] = d[u];
    }
    for (auto [v, w] : adj[u])  { 
        if (v != p) {
            d[v] = d[u] + w;
            DepthFirstSearch(v, u);
            x[u] = min(x[u], x[v]);
        }
    }
    out[u]=t - 1;
    dp[u] = (x[u] == inf ? inf : x[u] - 2 * d[u]);
    dp2[u][0] = dp[u];
}

bool inside(int u, int from){
	return (in[u]<=in[from] && out[u] >= out[from]);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s >> q >> e;
	for (int i=0 ; i < n - 1; i++){
		int a,b,w;
		cin >> a >> b >> w;
		adj[a].pb(mp(b,w));
		adj[b].pb(mp(a,w));
		id[i+1] = mp(a,b);
	}
	for(int i = 0; i < s; ++i){
		int j;cin >> j;
		shop[j]=1;
	}
	DepthFirstSearch(e,e);
	for (int i = 1; i<20; i++){
		for (int j = 1; j<=n; j++){
			up[j][i] = up[up[j][i-1]][i-1];
			dp2[j][i] = min(dp2[j][i-1], dp2[up[j][i-1]][i-1]);
		}
	}
	while(q--){
		int i, r;
        cin >> i >> r;
        auto [u, v] = id[i];
        if (inside(u, v)) {
            swap(u, v);
        }
        if (!inside(u, r)) {
            cout << "escaped\n";
        } else {
            i64 best = dp[u], dd = d[r];
            for (int b = 19; b >= 0; b--) {
                if (inside(u, up[r][b])) {
                    best = min(best, dp2[r][b]);
                    r = up[r][b];
                }
            }
            if (best == inf) {
                cout << "oo\n";
            } else {
                cout << dd + best << '\n';
            }
        }
	}
	return 0;
}

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