Submission #1240232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240232		sh1ft	Valley (BOI19_valley)	C++17	100 / 100	244 ms	38884 KiB

valley

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

using namespace std;

const int mxN = 1e5+5, mxL = 20;

int N, S, Q, E, up[mxL][mxN], dep[mxN];
bool shp[mxN];
ll dis[mxN], dp[mxN], mup[mxL][mxN];
vector <pair <int, ll>> adj[mxN];
pair <int, int> EDGE[mxN];

ll dfs(int u, int p) {
    ll mn = LLONG_MAX;
    if (shp[u]) mn = dis[u];
    for (auto [v, w] : adj[u]) if (v != p) {
        dis[v] = dis[u] + w;
        dep[v] = dep[u] + 1;
        up[0][v] = u;
        mn = min(mn, dfs(v, u));
    }
    if (mn < LLONG_MAX) dp[u] = -2*dis[u] + mn;
    else dp[u] = LLONG_MAX;
    mup[0][u] = dp[u];
    return mn;
}

int main() {
    cin >> N >> S >> Q >> E;
    for (int i = 1; i < N; i++) { int u, v; ll w; cin >> u >> v >> w; adj[u].emplace_back(v, w), adj[v].emplace_back(u, w); EDGE[i] = make_pair(u, v); }
    for (int i = 0; i < S; i++) { int x; cin >> x; shp[x] = 1; }
    dep[E] = 1;
    dfs(E, E);
    for (int c = 1; c < mxL; c++) for (int i = 1; i <= N; i++) {
        up[c][i] = up[c-1][up[c-1][i]];
        mup[c][i] = min(mup[c-1][i], mup[c-1][up[c-1][i]]);
    }
    while (Q--) {
        int idx, x, p; cin >> idx >> x;
        if (dep[EDGE[idx].first] < dep[EDGE[idx].second]) p = EDGE[idx].second;
        else p = EDGE[idx].first;
        int t = x, k = dep[t] - dep[p];
        if (k < 0) { cout << "escaped\n"; continue; }
        for (int i = 0; i < mxL; i++) if (k & (1 << i)) t = up[i][t];
        if (t != p) { cout << "escaped\n"; continue; }
        t = x; k++;
        ll mn = LLONG_MAX;
        for (int i = 0; i < mxL; i++) if (k & (1 << i)) mn = min(mn, mup[i][t]), t = up[i][t];
        if (mn == LLONG_MAX) { cout << "oo\n"; continue; }
        cout << dis[x] + mn << '\n';
    }
}

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