Submission #1314773

#TimeUsernameProblemLanguageResultExecution timeMemory
1314773a5a7Valley (BOI19_valley)C++20
23 / 100
197 ms40896 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int MAXN = 100005;
int up[MAXN][20];
int path[MAXN];
ll depth[MAXN];
int ed[MAXN];
bool shop[MAXN];
ll sh[MAXN];
ll dp[MAXN][20];
vector<vector<pair<int,pair<ll,int>>>> v;

void dfs(int x, int prev){
    up[x][0] = prev;
    for (auto nxt : v[x]){
        if (nxt.first == prev) continue;
        path[nxt.first] = path[x] + 1;
        depth[nxt.first] = depth[x] + nxt.second.first;
        ed[nxt.second.second] = nxt.first;
        dfs(nxt.first, x);
        if (sh[nxt.first] != -1){
            sh[x] = min(sh[x], sh[nxt.first]+nxt.second.first);
        }
    }
    dp[x][0] = sh[x] == 1e18 ? 1e18 : sh[x] - depth[x];
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, s, q, e; cin >> n >> s >> q >> e;
    v.resize(n);
    fill(ed, ed+n, -1);
    for (int i = 1; i < n; i++){
        int a, b; ll w;
        cin >> a >> b >> w;
        a--, b--;
        v[a].push_back({b, {w, i}});
        v[b].push_back({a, {w, i}});
    }
    fill(shop, shop+n, 0);
    fill(sh, sh+n, 1e18);
    for (int i = 0; i < s; i++){
        int sho; cin >> sho;
        sho--;
        shop[sho] = 1;
        sh[sho] = 0;
    }
    e--;
    path[e] = 0;
    depth[e] = 0;
    dfs(e, -1);
    ll mini = 1e18;
    for (int i = 1; i < 20; i++){
        for (int j = 0; j < n; j++){
            up[j][i] = up[j][i-1] == -1 ? -1 : up[up[j][i-1]][i-1];
            dp[j][i] = up[j][i-1] == -1 ? dp[j][i-1] : max(dp[j][i-1], dp[up[j][i-1]][i-1]);
        }
    }
    for (int i = 0; i < q; i++){
        int a, b; cin >> a >> b;
        b--;
        a = ed[a];
        ll prev = depth[b];
        ll res = min(dp[a][0]+prev, sh[b]);
        if (path[a] > path[b]){
            cout << "escaped\n";
            continue;
        }
        for (int j = 0; j < 20; j++){
            if ((1<<j)&(path[b]-path[a])){
                res = min(res, dp[b][j] + prev);
                b = up[b][j];
            }
        }
        if (b != a){
            cout << "escaped\n";
        }else if (res == mini){
            cout << "oo\n";
        }else{
            cout << (res) << "\n";
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...