Submission #683182

#	Time	Username	Problem	Language	Result	Execution time	Memory
683182		finn__	Valley (BOI19_valley)	C++17	100 / 100	546 ms	61832 KiB

valley

#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<unsigned, uint64_t>>> g;
vector<unsigned> height;
vector<bool> is_shop;
vector<uint64_t> parent_dis, subtree_shop_dis;
vector<vector<unsigned>> anc;

void trav(unsigned u, vector<unsigned> &path, unsigned p = -1, unsigned h = 0)
{
    height[u] = h;
    subtree_shop_dis[u] = UINT64_MAX;

    for (size_t i = 1; i <= path.size(); i <<= 1)
        anc[u].push_back(path[path.size() - i]);
    path.push_back(u);

    for (auto const &[v, w] : g[u])
    {
        if (v != p)
        {
            trav(v, path, u, h + 1);
            if (subtree_shop_dis[v] != UINT64_MAX)
                subtree_shop_dis[u] =
                    min(subtree_shop_dis[u], subtree_shop_dis[v] + w);
            parent_dis[v] = w;
        }
    }

    path.pop_back();
    if (is_shop[u])
        subtree_shop_dis[u] = 0;
}

unsigned lift(unsigned u, unsigned h)
{
    size_t z = 0;
    while (h)
    {
        if (h & 1)
            u = anc[u][z];
        z++;
        h >>= 1;
    }
    return u;
}

size_t lg(size_t n)
{
    return 32 - __builtin_clz(n);
}

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

    size_t n, s, q, e;
    cin >> n >> s >> q >> e;
    e--;

    g = vector<vector<pair<unsigned, uint64_t>>>(n);
    vector<pair<unsigned, unsigned>> edges;
    for (size_t i = 0; i < n - 1; i++)
    {
        unsigned u, v;
        uint64_t w;
        cin >> u >> v >> w;
        g[u - 1].emplace_back(v - 1, w);
        g[v - 1].emplace_back(u - 1, w);
        edges.emplace_back(u - 1, v - 1);
    }

    is_shop = vector<bool>(n, 0);
    for (size_t i = 0; i < s; i++)
    {
        unsigned j;
        cin >> j;
        is_shop[j - 1] = 1;
    }

    height = vector<unsigned>(n);
    parent_dis = vector<uint64_t>(n);
    subtree_shop_dis = vector<uint64_t>(n, UINT64_MAX);
    anc = vector<vector<unsigned>>(n);
    vector<unsigned> path;
    trav(e, path);

    vector<vector<uint64_t>> shop_dis(n), dis(n);
    for (size_t i = 0; i < n; i++)
    {
        if (i != e)
        {
            shop_dis[i].push_back(subtree_shop_dis[i]);
            if (subtree_shop_dis[anc[i][0]] != UINT64_MAX)
                shop_dis[i].back() =
                    min(shop_dis[i].back(), parent_dis[i] + subtree_shop_dis[anc[i][0]]);
            dis[i].push_back(parent_dis[i]);
        }
    }

    for (size_t j = 1; j < lg(n); j++)
        for (size_t i = 0; i < n; i++)
            if (j < anc[i].size())
            {
                shop_dis[i].push_back(shop_dis[i][j - 1]);
                if (shop_dis[anc[i][j - 1]][j - 1] != UINT64_MAX)
                    shop_dis[i].back() =
                        min(shop_dis[i].back(),
                            shop_dis[anc[i][j - 1]][j - 1] + dis[i][j - 1]);
                dis[i].push_back(dis[i][j - 1] + dis[anc[i][j - 1]][j - 1]);
            }

    for (size_t i = 0; i < q; i++)
    {
        size_t j, r;
        cin >> j >> r;
        j--, r--;

        auto [u, v] = edges[j];

        if (height[u] > height[v])
            swap(u, v);

        if (height[u] >= height[r])
        {
            cout << "escaped\n";
            continue;
        }

        if (lift(r, height[r] - height[v]) == v)
        {
            size_t h = height[r] - height[v], z = 0;
            uint64_t d = 0, min_shop_d = subtree_shop_dis[r];
            while (h)
            {
                if (h & 1)
                {
                    if (shop_dis[r][z] != UINT64_MAX)
                        min_shop_d = min(min_shop_d, shop_dis[r][z] + d);
                    d += dis[r][z];
                    r = anc[r][z];
                }
                h >>= 1;
                z++;
            }

            if (min_shop_d == UINT64_MAX)
                cout << "oo\n";
            else
                cout << min_shop_d << '\n';
        }
        else
        {
            cout << "escaped\n";
            continue;
        }
    }
}

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