Submission #489998

#	Time	Username	Problem	Language	Result	Execution time	Memory
489998		MohammadAghil	Valley (BOI19_valley)	C++14	100 / 100	241 ms	54128 KiB

valley

#include <bits/stdc++.h> 
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx,avx2")
using namespace std; 
typedef long long ll; 
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < r; i++)
#define per(i,r,l) for(int i = (r); i >= l; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define ss second 

const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 19, inf = 1e18 + 5;

int st[maxn], en[maxn], par[maxn][lg], t, h[maxn];
ll dp[maxn][lg], val[maxn][lg];
vector<pp> adj[maxn]; 
bool shop[maxn];
pp edge[maxn];

void dfs(int r, int p){
    par[r][0] = p;
    st[r] = t++;
    dp[r][0] = (!shop[r])*inf;
    for(pp c: adj[r]) if(c.ff != p){
        h[c.ff] = h[r] + 1;
        dfs(c.ff, r);
        val[c.ff][0] = c.ss;
        dp[r][0] = min(dp[r][0], dp[c.ff][0] + c.ss);
    }
    en[r] = t;
}

bool chkPar(int u, int p){
    return st[p] <= st[u] && en[p] >= en[u];
}

int main(){
    cin.tie(0) -> sync_with_stdio(false);
    // freopen("input.txt", "r", stdin);
    int n, s, q, e; cin >> n >> s >> q >> e; e--;
    rep(i,0,n-1){
        int u, v, w; cin >> u >> v >> w; u--, v--;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        edge[i] = {u, v};
    }
    rep(i,0,s){
        int t; cin >> t; t--;
        shop[t] = true;
    } 
    dfs(e, e);
    rep(i,0,n-1){
        if(!chkPar(edge[i].ff, edge[i].ss)){
            swap(edge[i].ff, edge[i].ss);
        }
    }
    rep(k,1,lg){
        rep(i,0,n){
            par[i][k] = par[par[i][k-1]][k-1];
            dp[i][k] = min(dp[i][k-1], dp[par[i][k-1]][k-1] + val[i][k-1]);
            val[i][k] = val[i][k-1] + val[par[i][k-1]][k-1];
        }
    }
    while(q--){
        int e, r; cin >> e >> r; e--, r--;
        int u = edge[e].ff;
        if(!chkPar(r, u)){
            cout << "escaped\n";
        }else{
            int d = h[r] - h[u] + 1;
            ll ans = inf, cr = 0;
            rep(k,0,lg){
                if(d>>k&1){
                    ans = min(ans, cr + dp[r][k]);
                    cr += val[r][k];
                    r = par[r][k];
                }
            }
            if(ans == inf) cout << "oo\n";
            else cout << ans << '\n';
        }
    }
    return 0;
}

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