Submission #877236

#	Time	Username	Problem	Language	Result	Execution time	Memory
877236		vjudge1	Valley (BOI19_valley)	C++17	100 / 100	213 ms	49164 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using piii = array<int, 3>;

#define pb push_back

const int LG = 18 + 2, N = 1e5 + 4;
const ll D = 1e15, INF = 1ll << 62;

struct Info {
    int anc;
    ll cost;
    Info () {
        anc = -1, cost = INF;
    }
} info[N][LG];

int n, s, q, e, down[N], h[N];
ll mnd[N], d[N];
bool shop[N];
vector<piii> g[N];

void dfs(int v = e) {    
    if (v != e) {
        for (int i = 1; i < LG; i++) {
            int u = info[v][i - 1].anc;
            if (u != -1)
                info[v][i].anc = info[u][i - 1].anc;
        }
    }

    for (auto [u, w, idx] : g[v]) {
        if (u != info[v][0].anc) {
            d[u] = d[v] + w;
            h[u] = h[v] +  1;
            down[idx] = u;
            info[u][0].anc = v;
            dfs(u);
            mnd[v] = min(mnd[v], mnd[u]);
        }
    }
    if (shop[v])
        mnd[v] = d[v];
}

void calcCost(int v = e) {
    info[v][0].cost = mnd[v] - (d[v] << 1);
    for (int i = 1; i < LG; i++) {
        int u = info[v][i - 1].anc;
        ll tmp = info[v][i - 1].cost;
        if (u != -1)
            tmp = min(tmp, info[u][i - 1].cost);
        info[v][i].cost = tmp;
    }

    for (auto [u, w, idx] : g[v]) 
        if (u != info[v][0].anc)
            calcCost(u);
}

int up(int v, int cnt) {
    for (int i = 0; i < LG; i++) 
        if (((1 << i) & cnt) && v != -1)
            v = info[v][i].anc;
    return v;
}

ll getMin(int v, int cnt) {
    ll ret = INF;
    for (int i = 0; i < LG; i++) {
        if (((1 << i) & cnt) && v != -1) {
            ret = min(ret, info[v][i].cost);
            v = info[v][i].anc;
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> s >> q >> e;
    for (int i = 0; i < n - 1; i++) {
        int v, u, w;
        cin >> v >> u >> w;
        v--, u--;
        g[v].pb({u, w, i});
        g[u].pb({v, w, i});
    }
    for (int i = 0; i < s; i++) {
        int v;
        cin >> v;
        v--;
        shop[v] = 1;
    }
    for (int i = 0; i < n; i++) 
        mnd[i] = INF;

    e--;
    dfs();
    calcCost();

    while (q--) {
        int edge, v;
        cin >> edge >> v;
        edge--, v--;
        int u = down[edge];

        int difh = h[v] - h[u];
        if (difh < 0 || up(v, difh) != u) 
            cout << "escaped";
        else {
            ll ans = getMin(v, difh + 1) + d[v];
            if (ans > D)
                cout << "oo";
            else
                cout << ans;
        }
        cout << '\n';
    }

    return 0;
}

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