Submission #942327

#	Time	Username	Problem	Language	Result	Execution time	Memory
942327		phoenix0423	Valley (BOI19_valley)	C++17	100 / 100	204 ms	50032 KiB

valley

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int INF = 1e18;
int n, s, q, e;
vector<pll> adj[maxn];
int succ[maxn][18], dep[maxn], ans[maxn], val[maxn][18], st[maxn];
int d[maxn];
pll edge[maxn];
void dfs(int pos, int prev){
    succ[pos][0] = prev;
    ans[pos] = (st[pos] ? 0 : INF);
    for(int i = 1; i < 18; i++) succ[pos][i] = succ[succ[pos][i - 1]][i - 1];
    for(auto [x, w] : adj[pos]){
        if(x == prev) continue;
        dep[x] = dep[pos] + 1;
        d[x] = d[pos] + w;
        dfs(x, pos);
        ans[pos] = min(ans[pos], ans[x] + w);
    }
}

void dfs2(int pos, int prev){
    val[pos][0] = ans[succ[pos][0]] - d[succ[pos][0]];
    for(int i = 1; i < 18; i++) val[pos][i] = min(val[pos][i - 1], val[succ[pos][i - 1]][i - 1]);
    for(auto [x, w] : adj[pos]){
        if(x == prev) continue;
        dfs2(x, pos);
    }
}
int lift(int b, int steps){
    for(int i = 17; i >= 0; i--){
        if(steps & (1 << i)) b = succ[b][i];
    }
    return b;
}

signed main(void){
    fastio;
    cin>>n>>s>>q>>e;
    e--;
    for(int i = 0; i < n - 1; i++){
        int a, b, w;
        cin>>a>>b>>w;
        a--, b--;
        edge[i].f = a, edge[i].s = b;
        adj[a].eb(b, w);
        adj[b].eb(a, w);
    }
    for(int i = 0; i < s; i++){
        int c;
        cin>>c;
        st[c - 1] = 1;
    }
    dfs(e, e);
    dfs2(e, e);
    for(int i = 0; i < q; i++){
        int id, r;
        cin>>id>>r;
        id--, r--;
        auto [a, b] = edge[id];
        if(dep[r] < dep[a] || dep[r] < dep[b] || lift(r, dep[r] - dep[a]) != a || lift(r, dep[r] - dep[b]) != b){
            cout<<"escaped\n";
            continue;
        }
        if(dep[a] > dep[b]) swap(a, b);
        int mn = ans[r];
        int dif = dep[r] - dep[b], pos = r;
        for(int i = 17; i >= 0; i--){
            if(dif & (1 << i)) mn = min(mn, val[pos][i] + d[r]), pos = succ[pos][i];
        }
        if(mn >= INF) cout<<"oo\n";
        else cout<<mn<<"\n";
    }
}

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