Submission #1161744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161744		son2008	Valley (BOI19_valley)	C++20	100 / 100	170 ms	51120 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define task "comseq"
#define ii pair<ll,ll>
#define fi first
#define se second
#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 20
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define fii fi.fi
#define fis fi.se3
#define sfi se.fi
#define see se.se
#define base 29
int dx[]={0LL,0LL,1,-1,1,1,-1,-1};
int dy[]={1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=1e5+1;
const int mod=1e9+7;
int d[maxn],n,S,q,e,P_min[maxn][lg2+1],dp[maxn],P[maxn][lg2+1],h[maxn],dist[maxn];
ii b[maxn];
vector<ii>a[maxn];
void dfs(int u,int cha)
{
    if(d[u])dp[u]=dist[u];
    else dp[u]=1e18;
    for(ii v:a[u])
    {
        if(v.fi==cha)continue;
        P[v.fi][0]=u;
        h[v.fi]=h[u]+1;
        dist[v.fi]=dist[u]+v.se;
        dfs(v.fi,u);
        dp[u]=min(dp[u],dp[v.fi]);
    }
    for(ii v:a[u])
    {
        if(v.fi==cha)continue;
        P_min[v.fi][0]=dp[u]-2*dist[u];
     //   cout<<dp[u]<<" "<<dp[u]-2*dist[u]<<" "<<u<<'\n';
    }
}
void build_lca(){
    for(int j=1;j<=lg2;j++){
        for(int i=1;i<=n;i++)
            if(P[i][j-1]!=0){
            P[i][j]=P[P[i][j-1]][j-1];
            P_min[i][j]=min(P_min[i][j-1],P_min[P[i][j-1]][j-1]);
            }
    }
}
int lca(int u,int v){
    if(h[u]<h[v])swap(u,v);
    for(int i=lg2;i>=0;i--){
        if(h[u]-h[v]>=(1<<i))
        u=P[u][i];
    }
    if(u==v){
        return u;
    }
    for(int i=lg2;i>=0;i--){
        if(P[u][i]!=P[v][i]){
            u=P[u][i];
            v=P[v][i];
        }
    }
    return P[u][0];
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if(fopen(task".inp","r")){
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);}
    cin>>n>>S>>q>>e;
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        a[u].push_back({v,w});
        a[v].push_back({u,w});
        b[i]={u,v};
    }
    for(int i=1;i<=S;i++)
    {
        int c;cin>>c;
        d[c]=1;
    }
    dfs(e,-1);
    build_lca();
    //cout<<P_min[1][2]<<'\n';
    while(q--)
    {
        int I,R;
        cin>>I>>R;
        int goc=R;
        int u=b[I].fi,v=b[I].se;
        if(h[u]>h[v])swap(u,v);
        if(lca(R,v)!=v)
        {
            cout<<"escaped"<<'\n';
        }
        else
        {
            int ans=dp[goc]-dist[goc];
            for(int j=lg2;j>=0;j--)
            {
                if((1<<j)<=h[R]-h[v])
                {
                    ans=min(ans,P_min[R][j]+dist[goc]);
                    R=P[R][j];
                }
            }
            if(ans>=1e15)cout<<"oo"<<'\n';
            else
            cout<<ans<<'\n';
        }
    }
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen(task".out","w",stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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