Submission #1318373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318373		wangzhiyi33	Valley (BOI19_valley)	C++20	100 / 100	214 ms	48956 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
const int maxn=1e5;

int n,s,qu,st;
int bin[maxn+2][20],mn[maxn+2][20];
int dep[maxn+2],dp[maxn+2],dist[maxn+2];
vector<pair<int,int> >adj[maxn+2];
bool shop[maxn+2];

void dfs(int cur,int par,int jrk){
    dp[cur]=1e18;
    dep[cur]=dep[par]+1; bin[cur][0]=par;
    dist[cur]=jrk;

    if(shop[cur]){
        dp[cur]=dist[cur];
    }

    for(auto [nxt,we] : adj[cur]){
        if(par==nxt)continue;
        dfs(nxt,cur,jrk+we);
        dp[cur]=min(dp[cur],dp[nxt]);
    }
    for(auto [nxt,we] : adj[cur]){
        if(par==nxt)continue;
       // mn[nxt][0]=min(mn[nxt][0],dp[cur]-2*dist[cur]);
    }

    mn[cur][0]=1e18;
    if(dp[cur]<1e18){
        mn[cur][0]=min(mn[cur][0],dp[cur]-2*dist[cur]);
    }
}

int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    int slsh=dep[u]-dep[v];

    for(int q=19;q>=0;q--){
        if(slsh>=(1<<q)){
            u=bin[u][q];
            slsh-=(1<<q);
        }
    }

    if(u==v)return u;
    for(int q=19;q>=0;q--){
        if(bin[u][q]!=bin[v][q]){
            u=bin[u][q],v=bin[v][q];
        }
    }
    return bin[u][0];
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>s>>qu>>st;
    ii edge[n+1];

    for(int q=1;q<n;q++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
        edge[q]={u,v};
    }
    for(int q=1;q<=s;q++){
        int x; cin>>x;
        shop[x]=true;
    }

    dfs(st,0,0);
    
    for(int q=1;q<=19;q++){
        for(int w=1;w<=n;w++){
            bin[w][q]=bin[bin[w][q-1]][q-1];
            mn[w][q]=min(mn[w][q-1],mn[bin[w][q-1]][q-1]);
        }
    }
    

    while(qu--){
        int jln,cur;
        cin>>jln>>cur;
        int idx=edge[jln].fir;
        if(dep[edge[jln].fir]<dep[edge[jln].sec]){
            idx=edge[jln].sec;
        }

        if(lca(idx,cur)!=idx){
            cout<<"escaped"<<endl;
            continue;
        }
        int ans=1e18;
        int slsh=dep[cur]-dep[idx]+1;
        int u=cur;

        for(int q=19;q>=0;q--){
            if(slsh>=(1<<q)){
                int cost=mn[u][q]+dist[cur];
                //cout<<u<<" "<<q<<" "<<mn[u][q]<<endl;
                ans=min(ans,cost);

                u=bin[u][q];
                slsh-=(1<<q);
            }
        }
        

        if(ans==1e18){
            cout<<"oo"<<endl;
        }
        else{
            cout<<ans<<endl;
        }
    }


}   

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