Submission #766943

#	Time	Username	Problem	Language	Result	Execution time	Memory
766943		normankr07	Valley (BOI19_valley)	C++17	100 / 100	261 ms	99728 KiB

valley

#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
const int N = 1e6;
ll ver, st, qry, rt;
vector<pair<int, ll>> adj[N];
ll tin[N], tout[N], dist[N], h[N], par[N], dp[N];
bool isst[N];
const int mlg = 32;
ll lca[N][36], dpbin[N][36];
ll timer = 0;

inline bool is_ancestor(int u, int v)
{
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}

void DFS1(int v, int p, int cw)
{
    tin[v] = ++timer;
    h[v] = h[p] + 1;
    dist[v] = cw;
    par[v] = p;
    for (auto [n, w] : adj[v])
        if (p != n)
        {
            DFS1(n, v, cw + w);
        }

    if (isst[v])
    {
        dp[v] = dist[v];
    }
    else
    {
        dp[v] = 1e18;
        for (auto [n, w] : adj[v])
            if (p != n)
                dp[v] = min(dp[v], dp[n]);
    }
    tout[v] = timer;
}

// void preprocess()
// {
//     for (int i = 1; i <= ver; i++)
//     {
//         if (i != par[i])
//         {
//             lca[i][0] = par[i];
//             if (dp[i] >= 1e18)
//                 dpbin[i][0] = 1e18;
//             else
//                 dpbin[i][0] = dp[i] - 2 * dist[i];
//         }
//     }

//     for (int vt = 1; vt <= ver; vt++)
//     {
//         for (int i = 1; i < mlg; i++)
//         {
//             lca[vt][i] = lca[lca[vt][i - 1]][i - 1];
//             dpbin[vt][i] = min(dpbin[vt][i - 1], dpbin[lca[vt][i - 1]][i - 1]);
//         }
//     }
// }

void preprocess(int v, int p)
{
    lca[v][0] = p;
    if (dp[v] == 1e18)
        dpbin[v][0] = 1e18;
    else
        dpbin[v][0] = dp[v] - 2 * dist[v];
    for (int i = 1; i < mlg; i++)
    {
        lca[v][i] = lca[lca[v][i - 1]][i - 1];
        dpbin[v][i] = min(dpbin[v][i - 1], dpbin[lca[v][i - 1]][i - 1]);
    }

    for (auto [n, w] : adj[v])
        if (n != p)
            preprocess(n, v);
}

ll qryf(int v, int b)
{
    if (!is_ancestor(v, b))
    {
        return -1;
    }
    int cw = dist[v];
    int k = h[v] - h[b];
    ll ans = 1e18;
    int u = v;
    for (int j = mlg - 1; j >= 0; --j)
        if (k & (1 << j))
        {
            ans = min(ans, dpbin[u][j]);
            u = lca[u][j];
        }
    ans = min(ans, dpbin[u][0]);
    // ans += ((ans == 1e18) ? 0 : cw);
    return ans + cw;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> ver >> st >> qry >> rt;
    vector<pair<int, int>> edgelist;
    for (int i = 0; i < ver - 1; i++)
    {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edgelist.push_back({u, v});
    }
    for (int i = 0; i < st; i++)
    {
        int v;
        cin >> v;
        isst[v] = 1;
    }
    DFS1(rt, rt, 0);
    preprocess(rt, rt);
    while (qry--)
    {
        int ban, cur;
        cin >> ban >> cur;
        auto &[u, v] = edgelist[ban - 1];
        if (h[u] < h[v])
            swap(u, v);
        ll ans = qryf(cur, u);
        if (ans == -1)
            cout << "escaped";
        else if (ans >= 1e18)
            cout << "oo";
        else
            cout << ans;
        cout << '\n';
    }
}

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