Submission #708334

#	Time	Username	Problem	Language	Result	Execution time	Memory
708334		Deepesson	Valley (BOI19_valley)	C++17	100 / 100	270 ms	52300 KiB

valley

#include <bits/stdc++.h>
#define MAX 105000
using ll = long long;
typedef std::pair<ll,ll> pii;
std::vector<pii> con[MAX];
ll lift[MAX][20],prof[MAX],dist[MAX],plift[MAX][20],valr[MAX];
bool shops[MAX];
ll inf = 1LL<<60LL;
ll dfs(ll pos,ll prev,ll depth,ll d){
    prof[pos]=depth;
    dist[pos]=d;
    lift[pos][0]=prev;
    for(int i=1;i!=20;++i){
        lift[pos][i]=lift[lift[pos][i-1]][i-1];
    }
    ll min = inf;
    if(shops[pos])min=dist[pos];
    for(auto&x:con[pos]){
        if(x.first==prev)continue;
        min=std::min(min,dfs(x.first,pos,depth+1,d+x.second));
    }
    valr[pos]=min-(2LL*dist[pos]);
    return min;
}
void dfs2(int pos,int prev){
    plift[pos][0]=std::min(valr[pos],valr[lift[pos][0]]);
    for(int i=1;i!=20;++i){
        plift[pos][i]=std::min(plift[pos][i-1],plift[lift[pos][i-1]][i-1]);
    }
    for(auto&x:con[pos]){
        if(x.first==prev)continue;
        dfs2(x.first,pos);
    }
}
pii climb(int pos,int b){
    ll min=valr[pos];
    for(int i=19;i!=-1;--i){
        if(b&(1<<i)){
            min=std::min(min,plift[pos][i]);
            pos=lift[pos][i];
        }
    }
    return {pos,min};
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int N,S,Q,E;
    std::cin>>N>>S>>Q>>E;--E;
    std::vector<pii> conlis;
    for(int i=1;i!=N;++i){
        int a,b,c;
        std::cin>>a>>b>>c;
        --a;--b;
        con[a].push_back({b,c});
        con[b].push_back({a,c});
        conlis.push_back({a,b});
    }
    for(int i=0;i!=S;++i){
        int x;
        std::cin>>x;
        --x;
        shops[x]=1;
    }
    dfs(E,E,0,0);
    dfs2(E,E);
    for(int i=0;i!=Q;++i){
        int a,b;
        std::cin>>a>>b;
        --a;--b;
        pii bloq = conlis[a];
        int peq = bloq.first;
        if(prof[bloq.second]>=prof[bloq.first])peq=bloq.second;
        if(prof[peq]>prof[b]){
            std::cout<<"escaped\n";
            continue;
        }
        int dif = prof[b]-prof[peq];
        auto res = climb(b,dif);
        if(res.first!=peq){
            std::cout<<"escaped\n";
            continue;
        }
        ll ans = res.second+dist[b];
        if(ans<(1LL<<50LL)){
            std::cout<<ans<<"\n";
        }else
            std::cout<<"oo\n";
    }
}

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