Submission #847084

#	Time	Username	Problem	Language	Result	Execution time	Memory
847084		dungz	Valley (BOI19_valley)	C++17	100 / 100	191 ms	49312 KiB

valley

//dau tuyen
//dau tuyen
//dau tuyen
#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7,nmax=1e5+5;
ll cost[nmax],f[nmax],mn[nmax][25];
int h[nmax],up[nmax][25];
vector<pair<int,ll>> a[nmax];
bool str[nmax];
vector<pair<int,int>> edge;
void dfs(int u,int par)
{
    for(auto i:a[u])
    {
        if(i.fi!=par)
        {
            cost[i.fi]=cost[u]+i.se;
            h[i.fi]=h[u]+1;
            dfs(i.fi,u);
        }
    }
}
void dfs2(int u,int par)
{
    f[u]=MAX;
    if(str[u]) f[u]=cost[u];
    for(auto i:a[u])
    {
        if(i.fi!=par)
        {
            dfs2(i.fi,u);
            f[u]=min(f[u],f[i.fi]);
        }
    }
}
void dfs3(int u,int par)
{
    for(auto i:a[u])
    {
        if(i.fi!=par)
        {
            up[i.fi][0]=u;
            mn[i.fi][0]=f[u]-2*cost[u];
            for(int j=1;j<=20;j++)
            {
                up[i.fi][j]=up[up[i.fi][j-1]][j-1];
                mn[i.fi][j]=min(mn[i.fi][j-1],mn[up[i.fi][j-1]][j-1]);
            }
            dfs3(i.fi,u);
        }
    }
}
int main(){

    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,s,q,e;
    cin>>n>>s>>q>>e;
    edge.push_back({0,0});
    for(int i=1;i<=n-1;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        a[x].push_back({y,z});
        a[y].push_back({x,z});
        edge.push_back({x,y});
    }
    for(int i=1;i<=s;i++)
    {
        int x;
        cin>>x;
        str[x]=1;
    }
    dfs(e,0);
    dfs2(e,0);
    dfs3(e,0);
    while(q--)
    {
        int u,v;
        cin>>u>>v;
        if(h[edge[u].fi]>h[edge[u].se]) swap(edge[u].fi,edge[u].se);
//        cout<<h[edge[u].se]<<" "<<h[v]<<" "<<edge[u].se<<" "<<v<<endl;
        if(h[edge[u].fi]>=h[v])
        {
            cout<<"escaped"<<endl;
            continue;
        }
        int gap=-h[edge[u].se]+h[v];
//        cout<<"type2";
        int v2=v;
        for(int i=0;i<=20;i++)
        {
            if(gap&(1<<i))
            {
                gap-=(1<<i);
                v2=up[v2][i];
            }
        }
        if(v2!=edge[u].se)
        {
            cout<<"escaped"<<endl;
            continue;
        }
        gap=-h[edge[u].se]+h[v];
        ll ans=MAX;
        v2=v;
        for(int i=0;i<=20;i++)
        {
            if(gap&(1<<i))
            {
                gap-=(1<<i);
                ans=min(ans,cost[v]+mn[v2][i]);
                v2=up[v2][i];
            }
        }
//        cout<<f[v]<<" "<<cost[v]<<" "<<;
        ans=min(ans,f[v]-cost[v]);
        if(ans>1e15) cout<<"oo"<<endl;
        else cout<<ans<<endl;
     }
//     cout<<mn[5][1]<<cost[3]<<" "<<cost[4]<<" "<<cost[5]<<" "<<f[5];
}
/*

*/

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