Submission #1104736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104736		goldencheems	Valley (BOI19_valley)	C++17	100 / 100	210 ms	160328 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pu push_back
#define ll long long
typedef pair <ll,ll> ii;
const int N=1e6;
long long mod=1e16;
ll n,s,q,e,h,t;
ll a[N+1],b[N+1],d[N+10],t_in[N+10],t_out[N+10],dist[N+10],dep[N+10];
ll tt[21][N+10],gt[21][N+10];
struct canh{
    ll u,v,w;
    };
canh c[N+10];
vector <ii> adj[N+10];
bool o[N+10];
void dfs(int u,int p){
    t++;
    t_in[u]=t;
    for(int i=1;i<=20;i++){
        tt[i][u]=tt[i-1][tt[i-1][u]];
    }
    d[u]=mod;
    if(o[u]) d[u]=dist[u];
    for(auto x:adj[u]){
        ll v=x.fi,w=x.se;
        if(v==p) continue;
        dist[v]=dist[u]+w;
        dep[v]=dep[u]+1;
        tt[0][v]=u;
        dfs(v,u);
        d[u]=min(d[u],d[v]);
    }
    t_out[u]=t;
    if(d[u]!=mod) gt[0][u]=d[u]-2*dist[u];
    else gt[0][u]=mod;
}
bool totien(int u,int v){
    if(t_in[u]<=t_in[v] and t_out[u]>=t_out[v]) return true;
    return false;
    }
void tinh(){
    cin>>n>>s>>q>>h;
    for(int i=1;i<n;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        adj[u].pu({v,w});
        adj[v].pu({u,w});
        c[i].u=u,c[i].v=v,c[i].w=w;
    }
    for(int i=1;i<=s;i++){
        cin>>b[i];
        o[b[i]]=true;
    }
    dep[h]=1;
    dfs(h,0);
    for(int i=1;i<n;i++){
        if(t_in[c[i].v]<t_in[c[i].u]){
            swap(c[i].u,c[i].v);
        }
    }
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            gt[i][j]=min(gt[i-1][j],gt[i-1][tt[i-1][j]]) ;
        }
    }
    while(q--){
        int i,u;
        cin>>i>>u;
        int v=c[i].v;
        if(!totien(v,u)){
            cout<<"escaped\n";
            continue;
        }
        ll res=gt[0][v]+dist[u],rem=dist[u];
        for(int i=20;i>=0;i--){
            if(dep[tt[i][u]]>=dep[v]){
                res=min(res,rem+gt[i][u]);
                u=tt[i][u];
            }
        }
        if(res<mod) cout<<res<<'\n';
        else cout<<"oo\n";
    }
    }
int main(){
    //freopen("jday.inp","r",stdin);
    //freopen("jday.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    tinh();
    return 0;

}
//code của anh Nam đẹp trai nhất CHL

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