Submission #657166

#	Time	Username	Problem	Language	Result	Execution time	Memory
657166		ash_gamertable	Valley (BOI19_valley)	C++14	100 / 100	415 ms	74932 KiB

valley

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
#define fastio          ios_base::sync_with_stdio(0); cin.tie(0);
vector<vector<vi>> g;
vector<vi> edge;
vi shops;
int up[100009][21],logk=21,magic[100009],distE[100009],depth[100009],up_magic[100009][21];

void dep(int node,int p,int d,int dd){
    distE[node]=d;
    depth[node]=dd;
    for(auto x:g[node]) if(x[0]!=p) dep(x[0],node,d+x[1],dd+1);
}

void st(int node,int p){
    up[node][0]=p;
    up_magic[node][0]=min(magic[node],magic[p]);
    for(auto x:g[node]) if(x[0]!=p) st(x[0],node);
}

int dfs(int node,int p){
    int ans=inf;
    for(auto x:g[node]) if(x[0]!=p) ans=min(ans,dfs(x[0],node));
    if(shops[node]==1) ans=distE[node];
    return (magic[node]=ans);
}

int lift(int node,int dist){
    for(int k=logk-1;k>=0;k--){
        if((dist>>k)&1) node=up[node][k];
    }
    return node;
}

int lca(int a,int b){
    a=lift(a,depth[a]-min(depth[a],depth[b]));
    b=lift(b,depth[b]-min(depth[a],depth[b]));
    if(a==b) return a;
    for(int k=logk-1;k>=0;k--){
        if(up[a][k]!=up[b][k]) a=up[a][k],b=up[b][k];
    }
    return up[a][0];
}

int32_t main()
{
    fastio;
    int n,s,q,e,a,b,w;
    cin>>n>>s>>q>>e;
    edge.resize(n+1);
    g.resize(n+1);
    shops.assign(n+1,0);
    vector<vi> queries(q);
    for(int i=1;i<n;i++){
        cin>>a>>b>>w;
        g[a].pb({b,w});
        g[b].pb({a,w});
        edge[i]={a,b};
    }
    for(int i=0;i<s;i++){
        cin>>a;
        shops[a]=1;
    }
    for(int i=0;i<q;i++){
        cin>>a>>b;
        queries[i]={a,b};
    }
    dep(e,0,0,0);
    dfs(e,0);

    for(int i=1;i<=n;i++) 
        if(magic[i]!=inf) 
            magic[i]=magic[i]-(2*(distE[i]));

    st(e,0);


    for(int k=1;k<logk;k++){
        for(int i=1;i<=n;i++) 
        {
            up[i][k]=up[up[i][k-1]][k-1];
            up_magic[i][k]=min(up_magic[i][k-1],up_magic[up[i][k-1]][k-1]);
        }
    }
    for(int i=0;i<q;i++){
        int n1=edge[queries[i][0]][0],n2=edge[queries[i][0]][1],r=queries[i][1];
        if(depth[n1]>depth[n2]) swap(n1,n2);
        if(lca(r,n2)==n2 )
        {
            int h = depth[r]-depth[n2],ans=inf;
            if(shops[r]) ans=magic[r];
            for(int k=logk-1;k>=0;k--){
                if(((int)1 << k) & h) 
                {
                    ans=min(ans,up_magic[r][k]);
                    r=up[r][k];
                }
            }
            ans=min(ans,magic[n2]);
            if(ans==inf) cout<<"oo\n";
            else cout<<distE[queries[i][1]]+ans<<"\n";

        }
        else cout<<"escaped\n";
    }

return 0;
}

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