Submission #766640

#	Time	Username	Problem	Language	Result	Execution time	Memory
766640		normankr07	Valley (BOI19_valley)	C++17	0 / 100	318 ms	85268 KiB

valley

#include <bits/stdc++.h>
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][mlg], dpbin[N][mlg];
ll timer = 0;

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

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

    if (isst[v])
    {
        dp[v] = dist[v];
    }
    else
    {
        dp[v] = (ll)(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++)
    {
        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]);
        }
    }
}

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

int main()
{
    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();

    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: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41