Submission #134900

#	Time	Username	Problem	Language	Result	Execution time	Memory
134900		Bodo171	Valley (BOI19_valley)	C++14	100 / 100	599 ms	43640 KiB

valley

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
const long long inf=1LL*1e15;
vector< pair<int,int> > v[nmax];
vector<int> label[nmax];
long long lev[nmax],closest[nmax];
long long mn[20][nmax];
long long ans;
int tt[20][nmax];
int l[nmax],r[nmax],dpth[nmax],actual[nmax];
int nr,n,spec,q,root,i,x,y,z,j,blocat,nod,cat;
void dfs(int x)
{
    int nod=0;
    l[x]=++nr;
    for(int i=0;i<v[x].size();i++)
        if(!l[v[x][i].first])
    {
        nod=v[x][i].first;
        tt[0][nod]=x;dpth[nod]=dpth[x]+1;
        actual[label[x][i]]=nod;
        lev[nod]=1LL*lev[x]+v[x][i].second;
        dfs(nod);
        closest[x]=min(closest[x],closest[nod]+v[x][i].second);
    }
    r[x]=nr;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>spec>>q>>root;
    for(i=1;i<=n-1;i++)
    {
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
        label[x].push_back(i);
        label[y].push_back(i);
    }
    for(i=1;i<=n;i++)
        closest[i]=inf;
    for(i=1;i<=spec;i++)
    {
        cin>>x;
        closest[x]=0;
    }
    dfs(root);
    for(i=1;i<=n;i++)
        mn[0][i]=closest[i]-lev[i];
    for(i=1;i<=16;i++)
        for(j=1;j<=n;j++)
    {
        tt[i][j]=tt[i-1][tt[i-1][j]];
        mn[i][j]=min(mn[i-1][j],mn[i-1][tt[i-1][j]]);
    }
    for(i=1;i<=q;i++)
    {
        cin>>blocat>>x;
        y=actual[blocat];
        if(l[y]<=l[x]&&l[x]<=r[y])
        {
            ans=inf;cat=dpth[x]-dpth[y]+1;nod=x;
            for(int p=16;p>=0;p--)
              if(((1<<p)&cat))
            {
                ans=min(ans,mn[p][nod]+lev[x]);
                nod=tt[p][nod];
            }
            if(ans==inf) cout<<"oo\n";
            else cout<<ans<<'\n';
        }
        else cout<<"escaped\n";
    }
    return 0;
}

Compilation message (stderr)

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

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