제출 #1275415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275415		SoMotThanhXuan	Valley (BOI19_valley)	C++17	100 / 100	96 ms	37624 KiB

valley

/***ThanhCodeDao***/
/*****Azazel*****/
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define checkbit(mask,i) ((mask>>i)&1)
#define bit(i) (1<<i)
#define Mlog 17
typedef long long ll;
const ll maxN = 1e5+3 ,modd = 1e9+7;
int n,s,q,r;
vector<pair<int,int>> adj[maxN];
pair<int,int> e[maxN];
int st[maxN], fn[maxN], cnt = 0, pa[Mlog+1][maxN];
ll h[maxN], d[maxN];
ll near[maxN], mind[Mlog+1][maxN];
void pre_dfs(int u,int par){
    st[u] = ++cnt;
    for(pair<int,int> pp : adj[u]){
        int v = pp.F, w = pp.S;
        if(v==par) continue;
        d[v] = d[u] + w;
        h[v] = h[u] + 1;
        pa[0][v] = u;
        pre_dfs(v,u);
        near[u] = min(near[u], near[v] + w);
    }
    fn[u] = cnt;
}
bool checkpar(int u,int v){
    return (st[u] <= st[v] and fn[v] <= fn[u]);
}
void solve(){
    cin >> n >> s >> q >> r;
    for(int i = 1;i<=n;i++) near[i] = 1e18;
    for(int i = 1;i<=n-1;i++){
        int u,v,w; cin >> u >> v >> w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
        e[i] = {u,v};
    }
    for(int i = 1;i<=s;i++){
        int c; cin >> c;
        near[c] = 0;
    }
    pre_dfs(r,0);
    for(int i = 1;i<=n-1;i++){
        if(st[e[i].F] > st[e[i].S]) swap(e[i].F,e[i].S);
    }
    for(int i = 1;i<=n;i++){
        mind[0][i] = near[i] - d[i];
    }
    for(int i = 1;i<=Mlog;i++){
        for(int j = 1;j<=n;j++){
            pa[i][j] = pa[i-1][pa[i-1][j]];
            mind[i][j] = min(mind[i-1][j], mind[i-1][pa[i-1][j]]);
        }
    }
    while(q--){
        int id,pos;
        cin >> id >> pos;
        int v = e[id].S;
        if(!checkpar(v,pos)){
            cout << "escaped" << '\n';
            continue;
        }
        int kc = h[pos] - h[v] + 1;
        ll res = 1e18;
        int u = pos;
        for(int i = 0;i<=Mlog;i++){
            if(checkbit(kc,i)){
                res = min(res, mind[i][u]);
                u = pa[i][u];
            }
        }
        res += d[pos];
        if(res > 1e17){
            cout << "oo" << '\n';
            continue;
        }
        cout << res << '\n';
    }

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
}

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