Submission #1182204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182204		Matbubble	Valley (BOI19_valley)	C++20	100 / 100	140 ms	52076 KiB

valley

#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";

/*  
xdxd
*/
const long long maxN=1e5;
vector<pair<long long, long>>g[maxN+1];
bool tienda[maxN+1];
long long min_dis[maxN+1];
long long dis[maxN+1];

long long bl[maxN+1][21];
long long dp[maxN+1][21];
long long tin[maxN+1], tout[maxN+1], depth[maxN+1];
long long cont=0;
void dfs(long long u, long long root){
    long long mini=1e18;
    if(tienda[u]==1) mini=0;
    bl[u][0]=root;
    for(long long i=1 ; i<20 ; i++){
        bl[u][i]=bl[bl[u][i-1]][i-1];
    }
    // dbg(cont)
    tin[u]=++cont;
    for(auto v:g[u]){
        if(v.first==root) continue;
        dis[v.first]=dis[u]+v.second;
        depth[v.first]=depth[u]+1;
        dfs(v.first, u);
        mini=min(mini, min_dis[v.first]+v.second);
    }
    tout[u]=++cont;
    min_dis[u]=mini;
}


bool papi(long long u, long long v){
    return tin[u]<=tin[v] && tout[u]>=tout[v];
}

long long lca(long long u, long long v){
    // dbg("pene")
    if(papi(u, v)) return u;
    if(papi(v, u)) return v;
    for(long long l=19 ; l>=0 ; l--){
        // dbg(l)
        if(papi(bl[u][l], v)==false){
            u=bl[u][l];
        }
    }
    return bl[u][0];
}

long long distancia(long long u, long long v){
    return dis[v]-dis[u];
}

void pre(long long u, long long root){
    dp[u][0]=min(min_dis[u], min_dis[root]+distancia(root, u));
    for(long long l=1 ; l<20 ; l++){
        dp[u][l]=min(dp[u][l-1], dp[bl[u][l-1]][l-1]+distancia(bl[u][l-1], u));
    }
    for(auto v:g[u]){
        if(v.first==root) continue;
        pre(v.first, u);
    }
}

void solve(){
    long long n, s, q, e; cin>>n>>s>>q>>e;
    vector<pair<long long, long long>>adj;
    for(long long i=1 ; i<n ; i++){
        long long a, b, w; cin>>a>>b>>w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
        adj.push_back({a, b});
    }
    for(long long i=0 ; i<s ; i++){
        long long a; cin>>a;
        tienda[a]=1;
    }
    for(long long i=0 ; i<=n ; i++){
        for(long long j=0 ; j<20 ; j++) bl[i][j]=e;
    }
    for(long long i=0 ; i<=n ; i++){
        for(long long j=0 ; j<20 ; j++) dp[i][j]=0;
    }
    dis[e]=0;
    depth[e]=0;
    dfs(e, e);
    pre(e, e);
    // for(long long i=0 ; i<=n ; i++){
    //     for(long long j=0 ; j<20 ; j++) cout<<dp[i][j]<<" ";
    //     cout<<"\n";
        
    // }
    // for(long long i=1 ; i<=n ; ?i++) dbg(min_dis[i])
    while(q--){
        long long I, R; cin>>I>>R;
        I--;
        long long one=adj[I].first, two=adj[I].second;
        if(depth[two]>depth[one]) swap(one, two);
        if(lca(one, R)==one){
            long long xd=R;
            long long init=min_dis[R];
            // dbg(min_dis[R]);
            for(long long l=19 ; l>=0 ; l--){
                if(papi(bl[R][l], one)==false || bl[R][l]==one){
                    // dbg(R)
                    // dbg(l)
                    // dbg(one)
                    // dbg(bl[R][l])
                    // dbg("----")¢
                    init=min(init, distancia(R, xd)+dp[R][l]);
                    R=bl[R][l];
                }
            }
            if(init==1e18) cout<<"oo\n";
            else cout<<init<<"\n";
        }else{
            cout<<"escaped\n";
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

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