Submission #898781

#	Time	Username	Problem	Language	Result	Execution time	Memory
898781		vjudge1	Valley (BOI19_valley)	C++17	36 / 100	90 ms	8392 KiB

valley

// Parsa Jokar 2023 https://github.com/phictus/ioi

#pragma GCC optimize("Ofast")

#include <iostream>
#include <limits>
#include <vector>
#include <queue>
#include <cstdint>

using namespace std;
using Pair = pair<int64_t, int64_t>;

struct Edge
{
    int64_t v, u, w;
};

constexpr int64_t maxn = 1000, inf = numeric_limits<int64_t>::max();
int64_t n, s, q, e, currentTime = 0, startTime[maxn + 1], finishTime[maxn + 1], dp[maxn][maxn + 1];
Edge edge[maxn];
vector<int64_t> adj[maxn + 1];
bool hasShop[maxn + 1];

void InitDiscovery(int64_t v = 1, int64_t p = 1)
{
    startTime[v] = currentTime++;
    for (int64_t i : adj[v])
    {
        int64_t u = edge[i].v + edge[i].u - v;
        if (u != p)
            InitDiscovery(u, v);
    }

    finishTime[v] = currentTime;
}

void InitDp(int64_t discard)
{
    priority_queue<Pair, vector<Pair>, greater<Pair>> q;
    vector isVisited = vector<bool>(n + 1, false);
    for (int64_t v = 1; v <= n; v++)
    {
        if (hasShop[v])
        {
            dp[discard][v] = 0;
            q.push(make_pair(0, v));
        }
        else
            dp[discard][v] = inf;
    }

    while (!q.empty())
    {
        int64_t v = q.top().second;
        q.pop();

        if (isVisited[v])
            continue;
        isVisited[v] = true;

        for (int64_t i : adj[v])
        {
            if (i == discard)
                continue;

            int64_t u = edge[i].v + edge[i].u - v;
            if (isVisited[u])
                continue;

            if (dp[discard][u] > dp[discard][v] + edge[i].w)
            {
                dp[discard][u] = dp[discard][v] + edge[i].w;
                q.push(make_pair(dp[discard][u], u));
            }
        }
    }
}

bool IsAncestor(int64_t v, int64_t u)
{
    return startTime[v] <= startTime[u] && finishTime[v] >= finishTime[u];
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> s >> q >> e;
    for (int64_t i = 1; i < n; i++)
    {
        cin >> edge[i].v >> edge[i].u >> edge[i].w;
        adj[edge[i].v].push_back(i);
        adj[edge[i].u].push_back(i);
    }

    InitDiscovery();
    for (int64_t i = 1; i < n; i++)
    {
        if (startTime[edge[i].v] > startTime[edge[i].u])
            swap(edge[i].v, edge[i].u);
    }

    for (int64_t i = 1; i <= s; i++)
    {
        int64_t v;
        cin >> v;
        hasShop[v] = true;
    }

    for (int64_t i = 1; i < n; i++)
        InitDp(i);

    while (q--)
    {
        int64_t i, v;
        cin >> i >> v;

        if ((IsAncestor(edge[i].u, v) ^ IsAncestor(edge[i].u, e)) == 0)
            cout << "escaped\n";
        else
        {
            if (dp[i][v] == inf)
                cout << "oo\n";
            else
                cout << dp[i][v] << '\n';
        }
    }

    return (0 ^ 0);
}

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