Submission #559766

#	Time	Username	Problem	Language	Result	Execution time	Memory
559766		hoanghq2004	Valley (BOI19_valley)	C++14	100 / 100	238 ms	41792 KiB

valley

#include <bits/stdc++.h>

using namespace std;

int n, m, q, root;
int in[100010], out[100010], ti, s[100010];
int par[100010][20];
long long rmq[100010][20], d[100010], dmin[100010];
pair <int, int> e[100010];
vector <pair <int, int> > adj[100010];

void dfs(int u, int p) {
    in[u] = ++ti;
    dmin[u] = (s[u] ? d[u] : 1e18);
    par[u][0] = p;
    for (int i = 1; i < 20; ++i)
        par[u][i] = par[par[u][i - 1]][i - 1];
    for (auto [v, w]: adj[u]) {
        if (v == p) continue;
        d[v] = d[u] + w;
        dfs(v, u);
        dmin[u] = min(dmin[u], dmin[v]);
    }
    out[u] = ti;
}

void initrmq(int u, int p) {
    rmq[u][0] = dmin[u] - 2 * d[u];
    for (int i = 1; i < 20; ++i)
        rmq[u][i] = min(rmq[u][i - 1], rmq[par[u][i - 1]][i - 1]);
    for (auto [v, w]: adj[u]) {
        if (v == p) continue;
        initrmq(v, u);
    }
}

int check(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}

long long get(int u, int w) {
    long long res = rmq[w][0];
    for (int i = 19; i >= 0; --i) {
        if (par[u][i] && check(w, par[u][i])) {
            res = min(res, rmq[u][i]);
            u = par[u][i];
        }
    }
    return res;
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> q >> root;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        e[i] = {u, v};
    }
    while (m--) {
        int u;
        cin >> u;
        s[u] = 1;
    }
    dfs(root, 0);
    initrmq(root, 0);
    while (q--) {
        int u, id;
        cin >> id >> u;
        int w = (check(e[id].first, e[id].second) ? e[id].second : e[id].first);
        if (!check(w, u)) cout << "escaped\n";
        else {
            long long ans = get(u, w);
            if (ans >= 1e16) cout << "oo\n";
            else cout << ans + d[u] << "\n";
        }
    }
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:18:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for (auto [v, w]: adj[u]) {
      |               ^
valley.cpp: In function 'void initrmq(int, int)':
valley.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for (auto [v, w]: adj[u]) {
      |               ^

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