Submission #1314372

#TimeUsernameProblemLanguageResultExecution timeMemory
1314372ghammazhassanValley (BOI19_valley)C++20
100 / 100
283 ms75412 KiB
// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define int long long
#define endl "\n"
#define fi first
#define se second
const int M=1e9+7;
const int inf = 1e14;
const int LOG=17;
const int N=1e5+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;
vector<pair<int,int>>a[N];
map<pair<int,int>,int>in;
map<int,pair<int,int>>it;
int sh[N];
int dp[LOG][N];
int di[N];
int vi[N];
int av[N];
int p[LOG][N];
int li[LOG][N];
void makest(){
    for (int j=1;j<LOG;j++){
        for (int i=1;i<=n;i++){
            p[j][i]=p[j-1][p[j-1][i]];
        }
    }
}
int bl(int x,int d){
    int k=LOG-1;
    while (k>=0){
        if ((1<<k)<=d){
            d-=1<<k;
            x=p[k][x];
        }
        k--;
    }
    return x;
}
void dfs(int x,int y){
    for (auto [i,w]:a[x]){
        if (i==y)continue;
        dfs(i,x);
        dp[0][x]=min(dp[0][x],dp[0][i]+w);
    }
}
void makst(){
    for (int j=1;j<LOG;j++){
        for (int i=1;i<=n;i++){
            li[j][i]=li[j-1][i]+li[j-1][p[j-1][i]];
        }
    }
    for (int j=1;j<LOG;j++){
        for (int i=1;i<=n;i++){
            dp[j][i]=min(dp[j-1][i],dp[j-1][p[j-1][i]]+li[j-1][i]);
        }
    }
}
int dis(int x,int d){
    int k=LOG-1;
    int c=0;
    int ans=inf;
    while (k>=0){
        if (d>=(1<<k)){
            ans=min(ans,c+dp[k][x]);
            c+=li[k][x];
            x=p[k][x];
            d-=1<<k;
        }
        k--;
    }
    ans=min(ans,c+dp[0][x]);
    return ans;
}
void solve(){
    int s,q,e;
    cin >> n >> s >> q >> e;
    for (int i=0;i<n-1;i++){
        cin >> x >> y >> w;
        a[x].push_back({y,w});
        a[y].push_back({x,w});
        in[{x,y}]=i;
        in[{y,x}]=i;
        it[i]={x,y};
    }
    for (int i=1;i<=n;i++){
        dp[0][i]=inf;
    }
    for (int i=0;i<s;i++){
        cin >> x;
        sh[x]=1;
        dp[0][x]=0;
    }
    queue<int>o;
    o.push(e);
    vi[e]=1;
    di[e]=1;
    while (o.size()){
        int h=o.front();
        o.pop();
        for (auto [i,w]:a[h]){
            if (vi[i])continue;
            vi[i]=1;
            di[i]=di[h]+1;
            li[0][i]=w;
            p[0][i]=h;
            o.push(i);
        }
    }
    makest();
    dfs(e,0);
    for (int i=1;i<=n;i++){
        if (dp[0][i]<inf){
            av[i]=1;
        }
        vi[i]=0;
    }
    makst();
    // cout << dis(5,1) << endl;
    for (int i=0;i<q;i++){
        int j,k;
        cin >> k >> j;
        k--;
        x=it[k].fi,y=it[k].se;
        if (di[x]>di[y])swap(x,y);
        if (di[y]>di[j]){
            cout << "escaped" << endl;
            continue;
        }
        if (bl(j,di[j]-di[y])!=y or bl(j,di[j]-di[x])!=x){
            cout << "escaped" << endl;
            continue;
        }
        if (av[y]){
            cout << dis(j,di[j]-di[y]) << endl;
        }
        else{
            cout << "oo" << endl;
        }
    }
}
signed main()    
{   
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r" ,stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed << setprecision(9);
    srand(time(0));
    // int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
        solve();
        q++;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...