Submission #558337

#	Time	Username	Problem	Language	Result	Execution time	Memory
558337		MayankGusain	Valley (BOI19_valley)	C++17	100 / 100	665 ms	59224 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 100000;
const int OO = 1e18;
int n, s, q, E, t = 0;

vector<int> inTime(N), outTime(N), shop(N), shopDistanceToE(N, OO), distanceToShop(N), distanceToE(N);
vector<pair<int, int>> e;
vector<vector<pair<int, int>>> g(N);
vector<vector<int>> binaryJumpVertex(N, vector<int>(18)), mn(N, vector<int>(18));

void dfs(int u, int p) {
    inTime[u] = t++;
    binaryJumpVertex[u][0] = p;
    if (shop[u]) {
        shopDistanceToE[u] = distanceToE[u];
    }
 
    for (auto [v, w] : g[u])  { 
        if (v != p) {
            distanceToE[v] = distanceToE[u] + w;
            dfs(v, u);
            shopDistanceToE[u] = min(shopDistanceToE[u], shopDistanceToE[v]);
        }
    }
 
    distanceToShop[u] = (shopDistanceToE[u] == OO ? OO : shopDistanceToE[u] - 2 * distanceToE[u]);
    mn[u][0] = distanceToShop[u];
    outTime[u] = t++;
}

bool is_ancestor(int u, int v) {
    return (inTime[u] <= inTime[v] && outTime[v] <= outTime[u]);
}

signed main() {
    cin >> n >> s >> q >> E;
    --E;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        e.emplace_back(u, v);
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    for (int i = 0; i < s; i++) {
        int u;
        cin >> u;
        shop[u - 1] = 1;
    }

    dfs(E, E);
    for (int b = 1; b < 18; b++) {
        for (int i = 0; i < n; i++) {
            binaryJumpVertex[i][b] = binaryJumpVertex[binaryJumpVertex[i][b - 1]][b - 1];
            mn[i][b] = min(mn[i][b - 1], mn[binaryJumpVertex[i][b - 1]][b - 1]);
        }
    }

    while (q--) {
        int i, r;
        cin >> i >> r;
        --i; --r;
        auto [u, v] = e[i];
        if (is_ancestor(u, v)) {
            swap(u, v);
        }
 
        if (!is_ancestor(u, r)) {
            cout << "escaped\n";
        } else {
            int best = distanceToShop[u], distanceRE = distanceToE[r];
            for (int b = 17; b >= 0; b--) {
                if (is_ancestor(u, binaryJumpVertex[r][b])) {
                    best = min(best, mn[r][b]);
                    r = binaryJumpVertex[r][b];
                }
            }
 
            if (best == OO) {
                cout << "oo\n";
            } else {
                cout << distanceRE + best << '\n';
            }
        }
    }
}

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