Submission #1094938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094938		vjudge1	Valley (BOI19_valley)	C++17	100 / 100	183 ms	89684 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using ll = long long;
const ll MAXN = 1e6 + 5;
const ll INF = 1e16;
const ll LOG = 30;
#define pll pair <ll, ll>
#define vll vector <ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " " << (x) << endl;

#define lc (pos<<1)
#define rc ((pos<<1)+1)
#define mid ((l+r)>>1)

ll n, s, q, e;
vector <vector <pll> > adj (MAXN);
array <ll, 3> edg [MAXN];
bool b [MAXN];
ll dep [MAXN], dis [MAXN], val [MAXN];
ll anc [MAXN][LOG], spa [MAXN][LOG];
vll lis;

void dfs(ll x, ll px){
    anc[x][0] = px;
    val[x] = INF;
    if(b[x]) val[x] = dis[x];
    for(auto nx : adj[x]){
        ll y = nx.fi, w = nx.se;
        if(y == px) continue;
        dep[y] = dep[x] + 1;
        dis[y] = dis[x] + w;
        dfs(y, x);
        val[x] = min(val[x], val[y]);
    }
    spa[x][0] = val[x] - (2*dis[x]);
    if(val[x] == INF) spa[x][0] = INF;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s >> q >> e;
    for(ll i = 1; i <= n-1; i++){
        ll u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edg[i] = {u, v, w};
    }
    for(ll i = 1; i <= s; i++){
        ll x; cin >> x; b[x] = 1;
    }
    dfs(e, 0);
    for(ll j = 1; j < LOG; j++){
        for(ll i = 1; i <= n; i++){
            anc[i][j] = anc[anc[i][j-1]][j-1];
            spa[i][j] = min(spa[i][j-1], spa[anc[i][j-1]][j-1]);
        }
    }
    for(ll i = 1; i <= q; i++){
        ll ed, x; cin >> ed >> x;
        ll u = edg[ed][0], v = edg[ed][1];
        if(dep[u] > dep[v]) swap(u, v);
        if(dep[x] < dep[v]){
            cout << "escaped" << endl;
            continue;
        }
        ll fw = x, mn = spa[fw][0];
        for(ll j = LOG-1; j >= 0; j--){
            if(dep[anc[fw][j]] >= dep[v]){
                mn = min(mn, spa[fw][j]);
                fw = anc[fw][j];
                mn = min(mn, spa[fw][0]);
            }
        }
        if(fw != v){
            cout << "escaped" << endl;
            continue;
        }
        if(mn == INF) cout << "oo" << endl;
        else cout << dis[x] + mn << endl;
    }
}

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