Submission #679254

#	Time	Username	Problem	Language	Result	Execution time	Memory
679254		stevancv	Valley (BOI19_valley)	C++14	100 / 100	212 ms	42604 KiB

valley

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int mod = 1e9 + 7;
const ll linf = 1e18;
int par[N][17];
ll mn[N][17];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, s, q, e;
    cin >> n >> s >> q >> e;
    e -= 1;
    vector<int> u(n), v(n), w(n);
    vector<vector<array<int, 2>>> g(n);
    for (int i = 0; i < n - 1; i++) {
        cin >> u[i] >> v[i] >> w[i];
        u[i] -= 1; v[i] -= 1;
        g[u[i]].push_back({v[i], i});
        g[v[i]].push_back({u[i], i});
    }
    vector<bool> is(n);
    for (int i = 0; i < s; i++) {
        int x; cin >> x; x -= 1;
        is[x] = 1;
    }
    vector<int> in(n), out(n), dep(n);
    int tsz = -1;
    vector<ll> opt(n, linf), pref(n);
    function<void(int, int, ll)> Dfs = [&] (int s, int e, ll o) {
        in[s] = ++tsz;
        pref[s] = o;
        par[s][0] = e;
        for (int i = 1; i < 17; i++) {
            if (par[s][i - 1] != -1) par[s][i] = par[par[s][i - 1]][i - 1];
            else par[s][i] = -1;
        }
        for (auto u : g[s]) {
            if (u[0] == e) continue;
            dep[u[0]] = dep[s] + 1;
            Dfs(u[0], s, o + w[u[1]]);
            smin(opt[s], opt[u[0]] + w[u[1]]);
        }
        if (is[s] == 1) opt[s] = 0;
        out[s] = tsz;
    };
    Dfs(e, -1, 0);
    for (int i = 0; i < n - 1; i++) {
        if (in[u[i]] > in[v[i]]) swap(u[i], v[i]);
    }
    for (int i = 0; i < n; i++) {
        if (opt[i] != linf) opt[i] -= pref[i];
    }
    function<void(int, int)> Dfs1 = [&] (int s, int e) {
        mn[s][0] = opt[s];
        for (int i = 1; i < 17; i++) {
            mn[s][i] = mn[s][i - 1];
            if (par[s][i - 1] != -1) smin(mn[s][i], mn[par[s][i - 1]][i - 1]);
        }
        for (auto u : g[s]) {
            if (u[0] == e) continue;
            Dfs1(u[0], s);
        }
    };
    Dfs1(e, -1);
    auto Get = [&] (int l, int r) {
        int kol = dep[r] - dep[l];
        ll ans = linf;
        for (int i = 16; i >= 0; i--) {
            if ((1 << i) & kol) {
                smin(ans, mn[r][i]);
                r = par[r][i];
            }
        }
        return min(opt[l], ans);
    };
    while (q--) {
        int x, y;
        cin >> x >> y;
         x -= 1; y -= 1;
         if (!(in[v[x]] <= in[y] && out[y] <= out[v[x]])) {
            cout << "escaped" << en;
            continue;
         }
         if (opt[v[x]] == linf) {
            cout << "oo" << en;
            continue;
         }
         ll ans = pref[y] + Get(v[x], y);
         cout << ans << en;
    }
    return 0;
}

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