Submission #1365295

#TimeUsernameProblemLanguageResultExecution timeMemory
1365295nariman_mt87Valley (BOI19_valley)C++20
23 / 100
133 ms52128 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long int
#define lli long long int
#define pii pair<ll,ll>
#define all(x) x.begin(),x.end()
#define mk make_pair
#define pb push_back
#define se  second
#define fi first
#define nn '\n'
#define lc (id << 1)
#define rc ((id << 1) ^ 1)
#define mid (l + r) / 2
#define txt freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define T int T;cin>>T;while(T--)
#define ashar(x) fixed<<setprecision(x)
#define migmig ios_base::sync_with_stdio(0);cin.tie(0);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const lli maxn = 2e5 + 10, mod = 998244353, sq = 400, lg = 22, inf = 1e18;
ll pw(ll a, ll b) { return (!b ? 1 : (b & 1 ? a * pw(a * a % mod, b / 2) % mod : pw(a * a % mod, b / 2) % mod)); }
ll n, m, s, q, r, k = 1;
ll up[lg][maxn], mn[lg][maxn], d[maxn], h[maxn], st[maxn], fn[maxn];
bool sh[maxn];
vector<pii> e[maxn], adj;
void dfs(ll v, ll par = r){
    st[v] = k++;
    d[v] = (sh[v] ? 0 : inf);
    up[0][v] = par;
    for(int i = 1; i < lg; i++){
        up[i][v] = up[i - 1][up[i - 1][v]];
    }
    for(auto [u, w] : e[v]){
        if(u != par){
            h[u] = h[v] + w;
            dfs(u, v);
            d[v] = min(d[v], d[u] + w);
        }
    }
    fn[v] = k;
}
void dfs2(ll v, ll par = r){
    mn[0][v] = d[v] - h[v];
    for(int i = 1; i < lg; i++){
        mn[i][v] = min(mn[i - 1][v], mn[i - 1][up[i - 1][v]]);
    }
    for(auto [u, w] : e[v]){
        if(u != par) dfs2(u, v);
    }
}
int main(){
    migmig;
    cin >> n >> s >> q >> r;
    ll u, v, w;
    for(int i = 1; i < n; i++){
        cin >> u >> v >> w;
        adj.pb({u, v});
        e[u].pb({v, w});
        e[v].pb({u, w});
    }
    for(int i = 1; i <= s; i++){
        cin >> v;
        sh[v] = 1;
    }
    dfs(r);
    dfs2(r);
    ll x;
    while(q--){
        cin >> x >> v;
        x--;
        if(st[v] < max(st[adj[x].fi], st[adj[x].se]) || st[v] >= min(fn[adj[x].fi], fn[adj[x].se])){
            cout << "escaped" << nn;
        }
        else{
            ll ans = d[v], u = v;
            for(int i = lg - 1; i >= 0; i--){
                if(h[up[i][u]] >= min(h[adj[x].fi], h[adj[x].se])){
                    ans = min(mn[i][u] + h[v], ans);
                    //cerr << mn[i][u] << " " << u << " " << i << " " << up[i][u] << nn;
                    u = up[i][u];
                }
            }
            if(ans == inf) cout << "oo" << nn;
            else cout << ans << nn; 
        }
    }
}
// Deathly mistakes:
//  * Read the problem carefully.
//  * Check maxn.
//  * Overflows.
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...