Submission #1290128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290128		Minbaev	Valley (BOI19_valley)	C++20	100 / 100	134 ms	70132 KiB

valley

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define int     long long
#define ar      array
#define mrand(a, b)   uniform_int_distribution<int>(a, b)(rng)

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 600000 + 5;
const int LOG = 20;
const int INF = (1LL<<60);

int n,m,k;
vector<int> tin(N), tout(N), dep(N), dp(N), type(N);
vector<ar<int,2>> g[N];
int p[N][LOG], val[N][LOG];
int timer;

int dfs(int x, int pr){
    tin[x] = ++timer;
    p[x][0] = pr;
    for(int i = 1;i<LOG;i++) p[x][i] = p[p[x][i-1]][i-1];
    int mn = INF;
    for(auto [to, cost] : g[x]){
        if(to == pr) continue;
        dep[to] = dep[x] + cost;
        umin(mn, dfs(to, x));
    }
    if(type[x]) umin(mn, dep[x]);
    if(mn == INF) dp[x] = INF;
    else dp[x] = mn - 2 * dep[x];
    tout[x] = ++timer;
    return mn;
}

void dfs2(int x, int pr){
    val[x][0] = min(dp[x], dp[pr]);
    for(int i = 1;i<LOG;i++) val[x][i] = min(val[x][i-1], val[p[x][i-1]][i-1]);
    for(auto [to, cost] : g[x]){
        if(to == pr) continue;
        dfs2(to, x);
    }
}

bool is_anc(int a, int b){
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int getMinOnPath(int u, int anc){
    if(u == anc) return dp[anc];
    int res = dp[u];
    for(int i = LOG-1;i>=0;i--){
        if(!is_anc(p[u][i], anc)){
            umin(res, val[u][i]);
            u = p[u][i];
        }
    }
    umin(res, val[u][0]);
    umin(res, dp[anc]);
    return res;
}

void solve(){
    int q;
    cin >> n >> m >> q >> k;
    for(int i=1;i<=n;i++){
        g[i].clear();
        type[i] = 0;
        dep[i] = 0;
        dp[i] = INF;
        tin[i] = tout[i] = 0;
        for(int j=0;j<LOG;j++) p[i][j] = i, val[i][j] = INF;
    }
    timer = 0;
    vector<ar<int,2>> vs;
    for(int i = 2;i<=n;i++){
        int a,b,c;
        cin >> a >> b >> c;
        g[a].pb({b, c});
        g[b].pb({a, c});
        vs.pb({a, b});
    }
    for(int i = 1;i<=m;++i){
        int a;
        cin >> a;
        type[a] = 1;
    }
    dfs(k, k);
    dfs2(k, k);
    while(q--){
        int a,b;
        cin >> a >> b;
        a -= 1;
        int e1 = vs[a][0], e2 = vs[a][1];
        if(dep[e1] >= dep[e2]) a = e1;
        else a = e2;
        if(!is_anc(a, b)){
            cout << "escaped\n";
            continue;
        }
        int ans = getMinOnPath(b, a);
        if(ans >= INF/4){
            cout << "oo\n";
        } else {
            cout << (ans + dep[b]) << "\n";
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int tt=1;
    while(tt--) solve();
    return 0;
}

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