Submission #647588

#	Time	Username	Problem	Language	Result	Execution time	Memory
647588		berr	Valley (BOI19_valley)	C++17	100 / 100	285 ms	64840 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<array<int, 2>> edge, adj[(int)(1e5+37)];
vector<int> dis((int)(1e5+37), 2e18), ee((int)1e5+7), depth((int)1e5+37);
int par[(int)1e5+37][26], mi[(int)1e5+37][26];
int tin[(int)1e5+37], tout[(int)1e5+37], cnt, val[(int)1e5+37];

void dfs(int v, int p, int gh, int de)
{
   // cout<<v<<cnt<<"\n";
    par[v][0]=p;
    ee[v]=gh;
    depth[v]=de;
    tin[v]=cnt;
    cnt++;
    for(auto i: adj[v])
    {
        int u=i[0], z=i[1];
        if(u==p) continue;
        dfs(u, v, gh+z, de+1);

        dis[v]=min(dis[v], dis[u]+z);
    }
  //  cout<<"o7"<<v<<cnt<<"\n";

    tout[v]=cnt;
    cnt++;
}

bool is_ancestor(int x, int y)
{
    if(tin[x]<=tin[y]&&tout[x]>=tout[y]) return 1;
    return 0;
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, s, q, e; cin>>n>>s>>q>>e;

    for(int i=0; i<n-1; i++)
    {
        int x, y, z; cin>>x>>y>>z;
        adj[x].push_back({y, z});
        adj[y].push_back({x, z});
        edge.push_back({x, y});

    }

    for(int i=0; i<=n; i++)
    {
        par[i][0]=i;
    }
    for(int i=0; i<s; i++)
    {

        int z; cin>>z;
        dis[z]=0;
    }
    for(int i=26; i>=0; i--)
    {
        for(int l=0; l<=n; l++)
        {
            mi[l][i]=2e18;
        }
    }
    dfs(e, e, 0, 0);

    for(int i=0; i<edge.size(); i++)
    {
        if(depth[edge[i][0]]<depth[edge[i][1]])
        {
            swap(edge[i][0], edge[i][1]);
        }
    }

    for(int l=1; l<26; l++)
    {
        for(int i=0; i<=n; i++)
        {
            par[i][l]=par[par[i][l-1]][l-1];
        }
    }

    for(int i=1; i<=n; i++)
    {
        val[i]=dis[i]-ee[i];
    }

    for(int l=0; l<=n; l++)
    {
        mi[l][0]=val[par[l][0]];
    }

    for(int l=1; l<26; l++)
    {
        for(int i=0; i<=n; i++)
        {
            mi[i][l]=min(mi[i][l-1], mi[par[i][l-1]][l-1]);
        }
    }

    while(q--)
    {
        int ed, pos; cin>>ed>>pos;
        ed--;
        if(!is_ancestor(edge[ed][0], pos)) cout<<"escaped\n";

        else
        {
            int x=edge[ed][0];
            int y=pos;
            int ans=val[pos];

            for(int j=25; j>=0; j--)
            {
                if(is_ancestor(x, par[pos][j]))
                {
                    ans=min(mi[pos][j], ans);
                    pos=par[pos][j];
                }
            }
            ans=min(ans, val[x]);
                        ans+=ee[y];

            if(ans<=1e18) cout<<ans<<"\n";
            else cout<<"oo\n";
        }
    }



}

Compilation message (stderr)

valley.cpp: In function 'int32_t main()':
valley.cpp:70:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0; i<edge.size(); i++)
      |                  ~^~~~~~~~~~~~

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