Submission #125549

#	Time	Username	Problem	Language	Result	Execution time	Memory
125549		The_Wolfpack	Valley (BOI19_valley)	C++14	100 / 100	505 ms	48376 KiB

valley

#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define ll long long
using namespace std;

const int NMAX=1e5+7;
const int LogNMAX=25;
const ll INF=1e18;

int n,s,q,E,tin[NMAX],tout[NMAX],par[LogNMAX][NMAX],lvl[NMAX];
vector<pii> g[NMAX];

ll dp[NMAX], dep[NMAX], mn[LogNMAX][NMAX];

struct edge{int a,b,w;};
edge e[NMAX];
int Time=0;
void Dfs(int son, int p, ll D)
{
    tin[son]=++Time;
    par[0][son]=p;
    dep[son]=D;
    for(pii i:g[son])
    {
        if(i.x==p) continue;
        lvl[i.x]=lvl[son]+1;
        Dfs(i.x, son, D+1LL*i.y);
        dp[son]=min(dp[son],dp[i.x]+1LL*i.y);
    }
    tout[son]=Time;
}

int ok(int A, int B)
{
    return tin[B]<=tin[A] && tout[B]>=tout[A];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n>>s>>q>>E;
    for(int i=0;i<=n;i++) dp[i]=INF;
    for(int i=1;i<=n-1;i++)
    {
        cin>>e[i].a>>e[i].b>>e[i].w;
        g[e[i].a].push_back({e[i].b, e[i].w});
        g[e[i].b].push_back({e[i].a, e[i].w});
    }
    while(s--)
    {
        int c; cin>>c;
        dp[c]=0;
    }
    Dfs(E,0,0);
    for(int i=1;i<=n;i++) if(par[0][e[i].a]==e[i].b) swap(e[i].a, e[i].b);
    for(int i=1;i<=n;i++) mn[0][i]=dp[i]-dep[i];
    for(int i=1;i<LogNMAX;i++) for(int j=1;j<=n;j++)
    {
        par[i][j]=par[i-1][par[i-1][j]];
        mn[i][j]=min(mn[i-1][j], mn[i-1][par[i-1][j]]);
    }
    while(q--)
    {
        int idx,node; cin>>idx>>node;
        idx=e[idx].b;
        if(!ok(node,idx))
        {
            cout<<"escaped"<<endl;
            continue;
        }
        ll res=INF;
        int idi=lvl[node]-lvl[idx]+1;
        int tmp=node;
        for(int i=0;i<LogNMAX;i++)
        {
            if(idi&(1<<i))
            {
                res=min(res,mn[i][node]);
                node=par[i][node];
            }
        }
        res+=dep[tmp];
        if(res>1e17+20) cout<<"oo"<<endl;
        else cout<<res<<endl;
    }
    return 0;
}

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