Submission #1232948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232948		chikien2009	Valley (BOI19_valley)	C++20	100 / 100	129 ms	35316 KiB

valley

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, s, q, e, a, b, c, pre[20][100000], head[100000], tail[100000];
long long val[20][100000], dist[100000], res;
vector<array<int, 3>> g[100000];
pair<int, int> edges[100000];
bool shop[100000];

inline bool IsPar(int par, int child)
{
    return head[par] <= head[child] && tail[child] <= tail[par];
}

inline void DFS(int node, int par)
{
    head[node] = a++;
    val[0][node] = (shop[node] ? dist[node] : 2e18);
    pre[0][node] = par;
    for (int i = 1; i < 20; ++i)
    {
        pre[i][node] = pre[i - 1][pre[i - 1][node]];
    }
    for (auto &i : g[node])
    {
        if (i[0] != par)
        {
            dist[i[0]] = dist[node] + i[1];
            DFS(i[0], node);
            val[0][node] = min(val[0][node], val[0][i[0]]);
        }
    }
    // cout << node << " " << dist[node] << " " << val[0][node] << "\n";
    tail[node] = a - 1;
}

inline void DFS1(int node, int par)
{
    val[0][node] -= 2 * dist[node];
    for (int i = 1; i < 20; ++i)
    {
        val[i][node] = min(val[i - 1][node], val[i - 1][pre[i - 1][node]]);
    }
    for (auto &i : g[node])
    {
        if (i[0] != par)
        {
            DFS1(i[0], node);
        }
    }
}

int main()
{
    setup();

    cin >> n >> s >> q >> e;
    e--;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b >> c;
        edges[i] = {a - 1, b - 1};
        g[a - 1].push_back({b - 1, c, i + 1});
        g[b - 1].push_back({a - 1, c, i + 1});
    }
    while (s--)
    {
        cin >> a;
        shop[a - 1] = true;
    }
    a = 0;
    DFS(e, e);
    DFS1(e, e);
    // return 0;
    while (q--)
    {
        cin >> a >> b;
        a--;
        b--;
        if (IsPar(edges[a].first, edges[a].second))
        {
            swap(edges[a].first, edges[a].second);
        }
        a = edges[a].first;
        if (IsPar(a, b))
        {
            c = b;
            res = 2e18;
            for (int i = 19; i >= 0; --i)
            {
                if (IsPar(a, pre[i][b]))
                {
                    res = min(res, dist[c] + val[i][b]);
                    b = pre[i][b];
                }
            }
            res = min(res, dist[c] + val[0][b]);
            cout << (res < 1e15 ? to_string(res) : "oo") << "\n";
        }
        else
        {
            cout << "escaped\n";
        }
    }
    return 0;
}

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