Submission #1365993

#TimeUsernameProblemLanguageResultExecution timeMemory
1365993kawhietValley (BOI19_valley)C++20
100 / 100
128 ms48636 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 47
#endif

#define int long long

constexpr int N = 1e5;
constexpr int inf = 1e18;

vector<pair<int, int>> g[N];
int par[N], lvl[N], tin[N], tout[N], up[N];

int timer = 0;

void init(int u, int p) {
    tin[u] = timer++;
    for (auto [v, w] : g[u]) {
        if (v != p) {
            up[v] = w;
            par[v] = u;
            lvl[v] = lvl[u] + 1;
            init(v, u);
        }
    }
    tout[u] = timer - 1;
}

bool is[N];
int dp[N], sum[N];

void dfs(int u, int p) {
    if (is[u]) {
        dp[u] = 0;
    }
    for (auto [v, w] : g[u]) {
        if (v != p) {
            sum[v] = sum[u] + w;
            dfs(v, u);
            dp[u] = min(dp[u], dp[v] + w);
        }
    }
}

struct HLD {
    int n, timer;
    vector<vector<int>> g;
    vector<int> sz, heavy, par, in, head;

    struct SegmentTree {
        int n;
        vector<int> t;

        void init(int _n) {
            n = _n;
            t.assign(4 * n, inf);
        }

        int merge(int x, int y) {
            return min(x, y);
        }

        void update(int id, int tl, int tr, int i, int v) {
            if (tl == tr) {
                t[id] = v;
                return;
            }
            int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
            if (i <= tm) {
                update(x, tl, tm, i, v);
            } else {
                update(y, tm + 1, tr, i, v);
            }
            t[id] = merge(t[x], t[y]);
        }

        int get(int id, int tl, int tr, int l, int r) {
            if (r < tl || tr < l) return inf;
            if (l <= tl && tr <= r) return t[id];
            int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
            return merge(get(x, tl, tm, l, r), get(y, tm + 1, tr, l, r));
        }

        void update(int i, int v) { update(0, 0, n - 1, i, v); }
        int get(int l, int r) { return get(0, 0, n - 1, l, r); }
    } t;

    HLD (int _n, vector<vector<int>> &_g) { init(_n, _g); }

    void init(int _n, vector<vector<int>> &_g) {
        n = _n;
        g = _g;
        sz.assign(n, 0);
        heavy.assign(n, -1);
        par.assign(n, -1);
        in.assign(n, 0);
        head.assign(n, 0);
        timer = 0; 
        dfs(0, -1);
        hld(0, 0);
        t.init(n);
    }

    void dfs(int u, int p) {
        sz[u] = 1;
        par[u] = p;
        int mx = 0;
        for (auto v : g[u]) {
            if (v == p) continue;
            dfs(v, u);
            sz[u] += sz[v];
            if (sz[v] > mx) {
                mx = sz[v];
                heavy[u] = v;
            }
        }
    }

    void hld(int u, int h) {
        in[u] = timer++;
        head[u] = h;
        if (heavy[u] != -1) {
            hld(heavy[u], h);
        }
        for (auto v : g[u]) {
            if (v == par[u] || v == heavy[u]) continue;
            hld(v, v);
        }
    }

    int get(int x, int y) {
        int ret = inf;
        while (head[x] != head[y]) {
            if (in[head[x]] < in[head[y]]) swap(x, y);
            ret = t.merge(ret, t.get(in[head[x]], in[x]));
            x = par[head[x]];
        }
        if (in[x] < in[y]) swap(x, y);
        ret = t.merge(ret, t.get(in[y], in[x]));
        return ret;
    }

    void update(int u, int x) {
        t.update(in[u], x);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, q, e;
    cin >> n >> k >> q >> e;
    vector<int> a(n - 1), b(n - 1), w(n - 1);
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        cin >> a[i] >> b[i] >> w[i];
        a[i]--; b[i]--;
        g[a[i]].push_back({b[i], w[i]});
        g[b[i]].push_back({a[i], w[i]});
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    for (int i = 0; i < n; i++) {
        dp[i] = inf;
    }
    for (int i = 0; i < k; i++) {
        int s;
        cin >> s;
        s--;
        is[s] = true;
    }
    e--;
    init(e, -1);
    dfs(e, -1);
    HLD h(n, adj);
    for (int i = 0; i < n; i++) {
        h.update(i, dp[i] - sum[i]);
    }
    while (q--) {
        int i, r;
        cin >> i >> r;
        i--; r--;
        int u = a[i], v = b[i];
        if (lvl[u] > lvl[v]) {
            swap(u, v);
        }
        if (tin[v] <= tin[r] && tin[r] <= tout[v]) {
            int res = h.get(r, v) + sum[r];
            if (res >= inf / 2) {
                cout << "oo\n";
            } else {
                cout << res << '\n';
            }
        } else {
            cout << "escaped\n";
        }
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...