Submission #879975

#	Time	Username	Problem	Language	Result	Execution time	Memory
879975		VectorLi	Valley (BOI19_valley)	C++17	100 / 100	106 ms	40520 KiB

valley

#include <bits/stdc++.h>
#define long long long

using namespace std;

const int V = (int) 1E5, K = 17;
const long MAX = numeric_limits<long>::max();

struct Element {
    long a;
};

const Element E = {MAX};

Element operator + (Element u, Element v) {
    Element w;
    w.a = min(u.a, v.a);
    return w;
}

int n, m, q, s;
vector<pair<int, long>> e1[V];
pair<int, int> e2[V - 1];
bool t[V];
int p[K][V], d1[V], h[V], l[V], c;
long d2[V], f[V];
Element g[K][V];

void DFS(int u) {
    h[u] = 1;
    l[u] = c;
    c = c + 1;
    f[u] = t[u] ? d2[u] : MAX;
    for (auto [v, w] : e1[u]) {
        if (v != p[0][u]) {
            p[0][v] = u;
            d1[v] = d1[u] + 1;
            d2[v] = d2[u] + w;
            DFS(v);
            h[u] = h[u] + h[v];
            f[u] = min(f[u], f[v]);
        }
    }
}

Element query(int u, int v) {
    Element x = E;
    if (d1[u] > d1[v]) {
        swap(u, v);
    }
    for (int i = K - 1; i >= 0; i--) {
        if ((d1[v] - d1[u]) >> i & 1) {
            x = x + g[i][v];
            v = p[i][v];
        }
    }
    if (u == v) {
        return x + g[0][u];
    }
    assert(false);
}

int lower(int i) {
    int u, v;
    tie(u, v) = e2[i];
    return d1[u] > d1[v] ? u : v;
}

void solve() {
    cin >> n >> m >> q >> s;
    s = s - 1;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        long w;
        cin >> u >> v >> w;
        u = u - 1, v = v - 1;
        e1[u].push_back({v, w});
        e1[v].push_back({u, w});
        e2[i] = {u, v};
    }
    for (int i = 0; i < m; i++) {
        int u;
        cin >> u;
        u = u - 1;
        t[u] = true;
    }

    p[0][s] = -1;
    DFS(s);
    for (int u = 0; u < n; u++) {
        if (f[u] < MAX) {
            f[u] = f[u] - d2[u] * 2;
        }
        g[0][u] = {f[u]};
    }

    for (int i = 0; i < K - 1; i++) {
        for (int u = 0; u < n; u++) {
            if (p[i][u] < 0) {
                p[i + 1][u] = -1;
                g[i + 1][u] = g[i][u];
            } else {
                p[i + 1][u] = p[i][p[i][u]];
                g[i + 1][u] = g[i][u] + g[i][p[i][u]];
            }
        }
    }

    for (int i = 0; i < q; i++) {
        int j;
        cin >> j;
        j = j - 1;
        int u, v;
        cin >> u;
        u = u - 1;
        v = lower(j);
        if (not (l[v] <= l[u] && l[v] + h[v] > l[u])) {
            cout << "escaped" << "\n";
        } else {
            Element x = query(u, v);
            if (x.a < MAX) {
                cout << d2[u] + x.a << "\n";
            } else {
                cout << "oo" << "\n";
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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