Submission #1370112

#TimeUsernameProblemLanguageResultExecution timeMemory
1370112Charizard2021Valley (BOI19_valley)C++20
0 / 100
276 ms32692 KiB
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<long long, long long> > > adj;
vector<pair<pair<long long, long long>, long long> > edges;
vector<bool> store;
vector<long long> nearest;
vector<long long> dist;
vector<long long> level;
vector<vector<long long> > dp;
void dfs(long long u, long long p){
    for(pair<long long, long long> x : adj[u]){
        long long v = x.first;
        if(v != p){
            dp[v][0] = u;
            dist[v] = dist[u] + x.second;
            level[v] = level[u] + 1;
            dfs(v, u);
            nearest[u] = min(nearest[u], nearest[v] + x.second);
        }
    }
    if(store[u]){
        nearest[u] = 0;
    }
}
long long binJump(long long u, long long val){
    for(long long j = 0; j < 21; j++){
        if(val & (1 << j)){
            u = dp[u][j];
        }
    }
    return u;
}
long long lca(long long a, long long b){
    if(level[a] > level[b]){
        swap(a, b);
    }
    b = binJump(b, level[b] - level[a]);
    long long low = 0;
    long long high = (1 << 20);
    long long res = -1;
    while(low <= high){
        long long mid = (low + high)/2;
        if(binJump(b, mid) == binJump(a, mid)){
            res = mid;
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
    }
    return binJump(b, res);
}
int main(){
    long long n, s, q, e;
    cin >> n >> s >> q >> e;
    adj.resize(1 + n);
    edges.resize(n);
    store.resize(1 + n);
    nearest.resize(1 + n, 1e18);
    dist.resize(1 + n);
    dp.resize(1 + n, vector<long long>(21, 0));
    level.resize(1 + n);
    for(long long i = 1; i < n; i++){
        long long a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back(make_pair(b, w));
        adj[b].push_back(make_pair(a, w));
        edges[i] = make_pair(make_pair(a, b), w);
    }
    for(long long i = 0; i < s; i++){
        long long x;
        cin >> x;
        store[x] = true;
    }
    dfs(e, 0);
    for(long long i = 1; i <= n; i++){
        for(long long j = 1; j < 21; j++){
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    while(q--){
        long long i, r;
        cin >> i >> r;
        long long u = edges[i].first.first;
        long long v = edges[i].first.second;
        if(dp[v][0] == u){
            swap(u, v);
        }
        if(lca(u, r) == u){
            if(nearest[u] == 1e9){
                cout << "oo\n";
            }
            else{
                if(s == n){
                    cout << 0 << "\n";
                }
                else{
                    long long ans = 1e18;
                    for(long long i = 1; i <= n; i++){
                        if(lca(u, i) == u && store[i]){
                            ans = min(ans, dist[r] + dist[i] - 2 * dist[lca(r, i)]);
                            // cout << u << " " << r << " " << i << " " << dist[r] + dist[i] - 2 * dist[lca(r, i)] << "\n";
                        }
                    }
                    cout << ans << "\n";
                }
            }
        }
        else{
            cout << "escaped\n";
        }
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...