Submission #1320401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320401		NgTrung2217	Valley (BOI19_valley)	C++20	100 / 100	117 ms	37680 KiB

valley

#include <bits/stdc++.h>
#define taskname ""
using namespace std;
using ld = long double;
using ull = unsigned long long;
using ll = long long;
const char el = '\n';
const char sp = ' ';
const ll inf = 1e18;
const ll maxN = 1e5 + 5;
const int LOG = 18;

int n, s, q, root, timer;
ll d[maxN], x[maxN], dp[maxN], tin[maxN], tout[maxN];
bool is_shop[maxN];
vector <pair <int, int>> adj[maxN];
pair <int, int> edge[maxN];
int up[maxN][LOG];
ll min_val[maxN][LOG];

void dfs(int u, int p)
{
    tin[u] = ++timer;
    up[u][0] = p;
    if (is_shop[u]) x[u] = d[u];
    else x[u] = inf;

    for (auto it : adj[u])
    {
        int v = it.first;
        int w = it.second;
        if (v != p)
        {
            d[v] = d[u] + w;
            dfs(v, u);
            x[u] = min(x[u], x[v]);
        }
    }

    if (x[u] == inf) dp[u] = inf;
    else dp[u] = x[u] - 2 * d[u];
    min_val[u][0] = dp[u];
    tout[u] = timer;
}

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

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen(taskname ".inp", "r"))
    {
        freopen(taskname ".inp", "r", stdin);
        freopen(taskname ".out", "w", stdout);
    }

    if (!(cin >> n >> s >> q >> root)) return 0;
    --root;

    for (int i = 1; i < n; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        edge[i] = {u, v};
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    for (int i = 0; i < s; ++i)
    {
        int u;
        cin >> u;
        is_shop[u - 1] = true;
    }

    dfs(root, root);

    for (int j = 1; j < LOG; ++j)
    {
        for (int i = 0; i < n; ++i)
        {
            up[i][j] = up[up[i][j - 1]][j - 1];
            min_val[i][j] = min(min_val[i][j - 1], min_val[up[i][j - 1]][j - 1]);
        }
    }

    while (q--)
    {
        int id, u;
        cin >> id >> u;
        --u;
        int x_edge = edge[id].first;
        int y_edge = edge[id].second;

        if (check(y_edge, x_edge)) swap(x_edge, y_edge);

        if (!check(y_edge, u)) cout << "escaped" << el;
        else
        {
            ll res = dp[y_edge];
            ll dist_u = d[u];
            int curr = u;
            for (int j = LOG - 1; j >= 0; --j)
            {
                if (check(y_edge, up[curr][j]))
                {
                    res = min(res, min_val[curr][j]);
                    curr = up[curr][j];
                }
            }

            if (res >= inf / 2) cout << "oo" << el;
            else cout << dist_u + res << el;
        }
    }

    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen(taskname ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(taskname ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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