Submission #203355

#	Time	Username	Problem	Language	Result	Execution time	Memory
203355		mdn2002	Valley (BOI19_valley)	C++14	100 / 100	807 ms	66552 KiB

valley

#include<bits/stdc++.h>
using namespace std;
long long n,s,q,e,st[100005][30],mn[100005][30],os[100005],di[100005],dp[100005],fo[100005],to[100005],sp[100005];
vector<pair<int,int> >gr[100005];
void dfs(int x,int p,long long dis)
{
    dp[x]=dp[p]+1;
    st[x][0]=p;
    di[x]=dis;
    os[x]=1e16;
    if(sp[x])os[x]=dis;
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i].first,w=gr[x][i].second;
        if(u==p)continue;
        dfs(u,x,dis+w);
        os[x]=min(os[x],os[u]);
    }
    mn[x][0]=os[x]-(2*dis);
}
bool ck(int x,int fr)
{
    int dif=dp[x]-dp[fr];
    if(dif<0)return 0;
    for(int i=0;i<=21;i++)
    {
        if((dif&(1<<i)))x=st[x][i];
    }
    if(x==fr)return 1;
    else return 0;
}
int main()
{
    cin>>n>>s>>q>>e;
    for(int i=0;i<n-1;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        fo[i]=x,to[i]=y;
        gr[x].push_back({y,w});
        gr[y].push_back({x,w});
    }
    for(int i=0;i<s;i++)
    {
        int x;
        cin>>x;
        sp[x]++;
    }
    dfs(e,0,0);
    for(int i=1;i<=25;i++)
    {
        for(int j=1;j<=n;j++)
        {
            st[j][i]=st[st[j][i-1]][i-1];
            mn[j][i]=min(mn[st[j][i-1]][i-1],mn[j][i-1]);
        }
    }
    while(q--)
    {
        int a,x;
        cin>>a>>x;
        a--;
        int fr;
        if(dp[fo[a]]<dp[to[a]])fr=to[a];
        else fr=fo[a];
        if(ck(x,fr)==0)
        {
            cout<<"escaped"<<endl;
            continue;
        }
        long long ans=1e18,nod=x;
        if(sp[x])ans=0;
        for(int i=21;i>=0;i--)
        {
            if(dp[st[nod][i]]>=dp[fr])
            {
                ans=min(ans,mn[nod][i]+di[x]);
                nod=st[nod][i];
            }
        }
        ans=min(ans,mn[fr][0]+di[x]);
        if(ans>1e15)cout<<"oo"<<endl;
        else cout<<ans<<endl;
    }
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int, long long int)':
valley.cpp:12:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[x].size();i++)
                 ~^~~~~~~~~~~~~

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