Submission #549169

#	Time	Username	Problem	Language	Result	Execution time	Memory
549169		krit3379	Valley (BOI19_valley)	C++17	100 / 100	200 ms	43832 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define N 100005

int tin[N],tout[N],depp[N],bp[20][N],t;
long long dp[N],dep[N],mi[20][N],ans;
pair<int,int> edge[N];
vector<pair<int,long long>> g[N];
// dp[i] lowest shop in i subtree

void dfs(int s,int f){
    tin[s]=++t;
    if(dp[s]==-1)dp[s]=dep[s];
    for(auto [x,w]:g[s]){
        if(x==f)continue;
        dep[x]=dep[s]+w;
        dfs(x,s);
        dp[s]=min(dp[s],dp[x]);
    }
    tout[s]=t;
}

void dfs2(int s,int f){
    depp[s]=depp[f]+1;
    bp[0][s]=f;
    mi[0][s]=dp[f]-2*dep[f];
    for(auto [x,w]:g[s]){
        if(x==f)continue;
        dfs2(x,s);
    }
}

int main(){
    int n,s,q,e,a,b,i,j,k,idx,r;
    long long w;
    scanf("%d %d %d %d",&n,&s,&q,&e);
    for(i=1;i<n;i++){
        scanf("%d %d %lld",&a,&b,&w);
        g[a].push_back({b,w});
        g[b].push_back({a,w});
        edge[i]={a,b};
        dp[i]=1e18;
    }
    dp[n]=1e18;
    for(i=1;i<=s;i++){
        scanf("%d",&k);
        dp[k]=-1;
    }
    dfs(e,0);
    dfs2(e,0);
    for(i=1;i<20;i++)for(j=1;j<=n;j++)bp[i][j]=bp[i-1][bp[i-1][j]],mi[i][j]=min(mi[i-1][j],mi[i-1][bp[i-1][j]]);
    while(q--){
        scanf("%d %d",&idx,&r);
        auto [a,b]=edge[idx];
        a=(depp[a]>depp[b])?a:b;
        if(tin[a]<=tin[r]&&tin[r]<=tout[a]){
            int dif=depp[r]-depp[a],temp=r;
            ans=dp[r]-dep[r];
            for(i=0;i<20;i++)if(dif&(1<<i))ans=min(ans,dep[r]+mi[i][temp]),temp=bp[i][temp];
            if(ans>1e16)printf("oo\n");
            else printf("%lld\n",ans);
        }
        else printf("escaped\n");
    }
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d %d %d %d",&n,&s,&q,&e);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%d %d %lld",&a,&b,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
valley.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d %d",&idx,&r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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