Submission #1344655

#TimeUsernameProblemLanguageResultExecution timeMemory
1344655minhtienValley (BOI19_valley)C++20
0 / 100
3095 ms15096 KiB
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,pair<ll,ll>>
#define fi first
#define se second
using namespace std;
const int N=1e5+5;
const ll inf=1e18;
vector<ii>v[N];
vector<iii>v2(N);
int n,s,q,e;
int a2[N];
int a1[N];
ll a4[N];
int p[N];
int a3[N];
ll dp[N];
vector<iii>v1(N);
int f(int x){
    if(x==p[x]) return x;
    return p[x]=f(p[x]);
}
void f1(int x,int y){
    int x1=f(x);
    int y1=f(y);
    if(x1!=y1){
        p[x1]=y1;
    }
}
void dick(){
    priority_queue<ii,vector<ii>,greater<ii>>q;
    for(int i=1;i<=s;i++){
        dp[a2[i]]=0;
        q.push({dp[a2[i]],a2[i]});
    }
    while(!q.empty()){
        ll s1=q.top().fi;
        int node=q.top().se;
        q.pop();
        if(s1>dp[node]) continue;
        for(auto x:v[node]){
            int node1=x.fi;
            ll s2=x.se;
            if(dp[node1]>dp[node]+s2){
                dp[node1]=dp[node]+s2;
                q.push({dp[node1],node1});
            }
        }
    }
}
void dick1(int s2){
    priority_queue<ii,vector<ii>,greater<ii>>q;
    q.push({dp[s2],s2});
    while(!q.empty()){
        ll s1=q.top().fi;
        int node=q.top().se;
        q.pop();
        if(s1>dp[node]) continue;
        for(auto x:v[node]){
            int node1=x.fi;
            ll s2=x.se;
            if(dp[node1]>dp[node]+s2){
                dp[node1]=dp[node]+s2;
                q.push({dp[node1],node1});
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin >>n >>s >>q >>e;
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    for(int i=1;i<=n-1;i++){
        int x,y,w;
        cin >>x >>y>>w;
        v2[i]={x,{y,w}};
    }
    for(int i=1;i<=s;i++){
        cin >> a2[i];
    }
    for(int i=1;i<=q;i++){
        int x,y;
        cin >>x >>y;
        v1[i]={x,{y,i}};
        a3[x]=1;
    }
    for(int i=1;i<=n;i++){
        dp[i]=inf;
    }
    for(int i=1;i<=n-1;i++){
        if(a3[i]==0){
            v[v2[i].fi].push_back({v2[i].se.fi,v2[i].se.se});
            v[v2[i].se.fi].push_back({v2[i].fi,v2[i].se.se});
            f1(v2[i].fi,v2[i].se.fi);
        }
    }
    dick();
    if(f(e)==f(v1[q].se.fi)) a4[q]=inf;
    else{
        if(dp[v1[q].se.fi]==inf) a4[q]=-inf;
        else a4[q]=dp[v1[q].se.fi];
    }
    int node=v2[v1[q].fi].fi,node1=v2[v1[q].fi].se.fi;
    ll w=v2[v1[q].fi].se.se;
    f1(node,node1);
    v[node].push_back({node1,w});
    v[node1].push_back({node,w});
    dick();
    dick1(node);
    dick1(node1);
    for(int i=q-1;i>=1;i--){
        if(f(e)==f(v1[i].se.fi)){
            a4[i]=inf;
        }
        else{
            if(dp[v1[i].se.fi]==inf){
                a4[i]=-inf;
            }
            else{
                a4[i]=dp[v1[i].se.fi];
            }
        }
        int node=v2[v1[i].fi].fi;
        int node1=v2[v1[i].fi].se.fi;
        ll w=v2[v1[i].fi].se.se;
        v[node].push_back({node1,w});
        v[node1].push_back({node,w});
        f1(node,node1);
        dick();
        dick1(node);
        dick1(node1);
    }
    for(int i=1;i<=q;i++){
        if(a4[i]==inf) cout << "escaped" << "\n";
        else if(a4[i]==-inf) cout << "oo" << "\n";
        else cout << a4[i] << "\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...