Submission #718567

#	Time	Username	Problem	Language	Result	Execution time	Memory
718567		fdnfksd	Valley (BOI19_valley)	C++14	100 / 100	242 ms	58316 KiB

valley

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll dp[maxN],in[maxN],out[maxN],tg=0;
bool c[maxN];
ll P[maxN][18];
const ll inf2=1e18;
struct qq
{
    ll fi,se,id;
};
vector<qq>g[maxN];
ll h[maxN],d[maxN];
ll val[maxN];
ll pos[maxN];
void cc(ll u,ll p)
{
    P[u][0]=p;
    for(int i=1;i<=17;i++) P[u][i]=P[P[u][i-1]][i-1];
    for(auto vv:g[u])
    {
        if(vv.fi!=p)
        {
            cc(vv.fi,u);
        }
    }
}
void dfs(ll u,ll p)
{
    dp[u]=inf;
    if(c[u]==1) dp[u]=0;
    in[u]=++tg;
    vector<pli>cc;
    for(auto vv:g[u])
    {
        if(vv.fi!=p)
        {
            pos[vv.id]=vv.fi;
            h[vv.fi]=h[u]+1;
            d[vv.fi]=d[u]+vv.se;
            dfs(vv.fi,u);
            dp[u]=min(dp[u],dp[vv.fi]+vv.se);
            cc.pb({dp[vv.fi]+vv.se,vv.fi});
        }
    }
    sort(cc.begin(),cc.end());
    if(c[u]==1)
    {
        for(auto vv:g[u])
        {
            if(vv.fi!=p)
            {
                val[vv.fi]=-d[u];
            }
        }
    }
    else
    {
        for(int i=0;i<min(2,(int)cc.size());i++)
        {
            for(auto vv:g[u])
            {
                if(vv.fi!=p&&vv.fi!=cc[i].se)
                {
                    val[vv.fi]=min(val[vv.fi],-d[u]+cc[i].fi);

                }
            }
        }
    }
    out[u]=tg;
}
ll mn[maxN][18];
void dfs2(ll u,ll p)
{
    mn[u][0]=val[u];
    for(int i=1;i<=17;i++) mn[u][i]=min(mn[u][i-1],mn[P[u][i-1]][i-1]);
    for(auto vv:g[u])
    {
        if(vv.fi!=p)
        {
            dfs2(vv.fi,u);
        }
    }
}
ll get(ll u,ll p)
{
    ll d=h[u]-h[p];
    ll ans=inf;
    for(int i=17;i>=0;i--)
    {
        if(d>>i&1)
        {
            ans=min(ans,mn[u][i]);
            u=P[u][i];
        }
    }
    return ans;
}
ll n,q,s,e;
bool ipar(ll u,ll p)
{
    return (in[p]<=in[u]&&out[u]<=out[p]);
}
void solve()
{
    cin >> n >> s >>  q >> e;
    for(int i=1;i<n;i++)
    {
        ll u,v,w;
        cin >> u >> v >> w;
        g[u].pb({v,w,i});
        g[v].pb({u,w,i});
    }
    for(int i=1;i<=n;i++) val[i]=inf,c[i]=0;
    for(int i=1;i<=s;i++)
    {
        ll u;
        cin >> u;
        c[u]=1;
    }
    cc(e,e);
    dfs(e,e);
    dfs2(e,e);
    while(q--)
    {
        ll id,u;
        cin >> id >> u;
        ll v=pos[id];
        if(ipar(u,v))
        {
            ll ans=inf;
            ans=min(ans,dp[u]);
            ans=min(ans,get(u,v)+d[u]);
            if(ans>=inf2) cout <<"oo\n";
            else cout << ans<<'\n';
        }
        else
        {
            cout <<"escaped\n";
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

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