Submission #1233035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233035		bbldrizzy	Valley (BOI19_valley)	C++20	100 / 100	186 ms	56984 KiB

valley

#include <bits/stdc++.h>
#define f first
#define ss second
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MX = 4*1e18;
const ll N = 1e5 + 5;
const ll LOG = 20;

ll n;                          // Number of nodes
vector<ll> adj[N];
vector<pair<ll, ll>> adj2[N];
ll val[N];                     // Value at each node
ll up[N][LOG];                 // up[v][i] = 2^i-th ancestor of v
ll min_up[N][LOG];             // min value along path to 2^i-th ancestor
ll depth[N];
ll cst[N];
vector<ll> amt;
ll es[N];

// DFS to initialize binary lifting tables
void dfs(ll v, ll p) {
    up[v][0] = p;
    min_up[v][0] = val[p];
    for (ll i = 1; i < LOG; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
        min_up[v][i] = min(min_up[v][i - 1], min_up[up[v][i - 1]][i - 1]);
    }
    if (adj[v].size() == 1 && v != p) {
        if (es[v]) {
            amt[v] = 0;
        } else {
            amt[v] = MX;
        }
    }
    if (es[v]) amt[v] = 0;
    // if (v == 1) {
    //     cout << "AMT: " << amt[v] << "\n"; 
    // }
    for (pair<ll, ll> u : adj2[v]) {
        if (u.f != p) {
            depth[u.f] = depth[v] + 1;
            cst[u.f ] = cst[v] + u.ss;
            dfs(u.f, v);
            // if (v == 1) {
            //     cout << "huh?:  " << u.f << ", " << v << "\n";
            // }
            amt[v] = min(amt[v], amt[u.f]+u.ss);
        }
    }
    // if (v == 1) {
    //     cout << "AMT: " << amt[v] << "\n"; 
    // }

}

// Find LCA of u and v
ll lca(ll u, ll v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (ll i = LOG - 1; i >= 0; --i)
        if (depth[u] - (1 << i) >= depth[v])
            u = up[u][i];
    if (u == v) return u;
    for (ll i = LOG - 1; i >= 0; --i)
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    return up[u][0];
}

// Min value from node u to ancestor anc (inclusive)
ll min_to_ancestor(ll u, ll anc) {
    ll res = val[u];
    for (ll i = LOG - 1; i >= 0; --i) {
        if (depth[u] - (1 << i) >= depth[anc]) {
            res = min(res, min_up[u][i]);
            u = up[u][i];
        }
    }
    return res;
}

// Min value along path u to v (inclusive)
ll min_on_path(ll u, ll v) {
    ll anc = lca(u, v);
    ll res = min(val[anc], min(min_to_ancestor(u, anc), min_to_ancestor(v, anc)));
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    ll n, s, q, e; cin >> n >> s >> q >> e; --e;
    amt.resize(n, MX);
    vector<pair<ll, ll>> edge;
    vector<ll> w;
    for (ll i = 0; i < n-1; i++) {
        ll a, b, c; cin >> a >> b >> c; --a; --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        adj2[a].push_back({b, c});
        adj2[b].push_back({a, c});
        edge.push_back({a, b});
        w.push_back(c);
    }
    for (ll i = 0; i < s; i++) {
        ll x; cin >> x; --x;
        es[x] = true;
    }
    dfs(e, e);
    for (ll i = 0; i < n; i++) {
        val[i] = amt[i]-cst[i];
    }
    dfs(e, e);
    while (q--) {
        ll i, r; cin >> i >> r; --i; --r; // i is road, r is village
        ll a = edge[i].f;
        ll b = edge[i].ss;
        if (depth[a] > depth[b]) {
            swap(a, b);
        }
        if (lca(b, r) == b) {
            ll val1 = cst[r];
            ll val2 = min_on_path(r, b);
            if (abs(val2) > 1e18) {
                cout << "oo";
            } else {
                // cout << val1 << ", " << val2 << "\n";
                cout << val1 + val2;
            }
        } else {
            cout << "escaped";
        }
        cout << "\n";
    }
}

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