Submission #980121

#	Time	Username	Problem	Language	Result	Execution time	Memory
980121		KLKLK	Valley (BOI19_valley)	C++17	100 / 100	159 ms	47632 KiB

valley

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

#define LL long long
#define PI pair<int, int>
#define VI vector<int>
#define VB vector<bool>
#define VL vector<LL>
#define VVPI vector<vector<PI>>

using namespace std;

void dfs(int v, int p, const VVPI &G, const VB &shop, VI &depth, VI &tin, VI &tout, VL &dist, VL &closest, VI &parent, int &timer)
{
    tin[v] = ++timer;
    parent[v] = p;
    if (shop[v]) closest[v] = dist[v];

    for (auto [u, d] : G[v])
    {
        if (u == p) continue;

        depth[u] = depth[v] + 1;
        dist[u] = dist[v] + (LL) d;

        dfs(u, v, G, shop, depth, tin, tout, dist, closest, parent, timer);
        closest[v] = min(closest[v], closest[u]);
    }

    tout[v] = ++timer;
}

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

    int n, s, q, r;
    cin >> n >> s >> q >> r;

    VVPI G(n + 1);
    vector<PI> edges(n);
    VB shop(n + 1);

    VI depth(n + 1);
    VI tin(n + 1);
    VI tout(n + 1);
    VL dist(n + 1);
    VL closest(n + 1, INT64_MAX);

    vector<VI> ancestor(20, vector<int>(n + 1));
    vector<VL> prefix(20, VL(n + 1));

    int a, b, c;
    for (int i = 1; i < n; ++i)
    {
        cin >> a >> b >> c;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
        edges[i] = {a, b};
    }

    for (int i = 0; i < s; ++i)
    {
        cin >> a;
        shop[a] = true;
    }

    dist[r] = 0ll;
    int timer = 0;
    dfs(r, 0, G, shop, depth, tin, tout, dist, closest, ancestor[0], timer);

    for (int v = 1; v <= n; ++v) closest[v] -= 2ll * dist[v];
    for (int v = 1; v <= n; ++v) prefix[0][v] = closest[ancestor[0][v]];

    for (int l = 1; l < 20; ++l)
    {
        for (int v = 1; v <= n; ++v)
        {
            ancestor[l][v] = ancestor[l - 1][ancestor[l - 1][v]];
            prefix[l][v] = min(prefix[l - 1][v], prefix[l - 1][ancestor[l - 1][v]]);
        }
    }

    int k, v;
    while (q--)
    {
        cin >> k >> v;
        auto [u, w] = edges[k];
        if (depth[u] < depth[w]) swap(u, w);

        if (tin[u] <= tin[v] && tout[v] <= tout[u])
        {
            LL res = closest[v];
            LL add = dist[v];

            for (int l = 19; l >= 0; --l)
            {
                if (tin[u] <= tin[ancestor[l][v]] && tout[ancestor[l][v]] <= tout[u])
                {
                    res = min(res, prefix[l][v]);
                    v = ancestor[l][v];
                }
            }

            res += add;
            if (res >= 1000000000000000ll) cout << "oo\n";
            else cout << res << "\n";
        }
        else cout << "escaped\n";
    }
}

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