Submission #1095532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095532		MateiKing80	Valley (BOI19_valley)	C++14	100 / 100	174 ms	56516 KiB

valley

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100000;
const ll inf = 1e18;
int n, s, q, e, t = 0;

vector<ll> in(N), out(N), magazin(N), x(N, inf), dp(N), d(N);
vector<pair<int, int>> much;
vector<vector<pair<int, int>>> vec(N);
vector<vector<ll>> lift(N, vector<ll>(18)), mn(N, vector<ll>(18));

void dfs(int u, int p)
{
    in[u] = t ++;
    lift[u][0] = p;
    if(magazin[u])
        x[u] = d[u];
    for(auto [v, w] : vec[u])
        if (v != p)
        {
            d[v] = d[u] + w;
            dfs(v, u);
            x[u] = min(x[u], x[v]);
        }
    dp[u] = (x[u] == inf ? inf : x[u] - 2 * d[u]);
    mn[u][0] = dp[u];
    out[u] = t ++;
}

bool is_ancestor(int u, int v)
{
    return (in[u] <= in[v] && out[u] >= out[v]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> s >> q >> e;
    e --;
    for(int i = 0; i < n - 1; i ++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u --;
        v --;
        much.emplace_back(u, v);
        vec[u].emplace_back(v, w);
        vec[v].emplace_back(u, w);
    }
    for(int i = 0; i < s; i ++)
    {
        int u;
        cin >> u;
        magazin[u - 1] = 1;
    }
    dfs(e, e);
    for(int b = 1; b < 18; b ++)
        for(int i = 0; i < n; i ++)
        {
            lift[i][b] = lift[lift[i][b - 1]][b - 1];
            mn[i][b] = min(mn[i][b - 1], mn[lift[i][b - 1]][b - 1]);
        }
    while(q --)
    {
        int i, r;
        cin >> i >> r;
        i --;
        r --;
        auto [u, v] = much[i];
        if(is_ancestor(u, v))
            swap(u, v);
        if(!is_ancestor(u, r))
            cout << "escaped\n";
        else
        {
            ll best = dp[u], dd = d[r];
            for(int b = 17; b >= 0; b --)
                if(is_ancestor(u, lift[r][b]))
                {
                    best = min(best, mn[r][b]);
                    r = lift[r][b];
                }
            if(best == inf)
                cout << "oo\n";
            else
                cout << dd + best << '\n';
        }
    }
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for(auto [v, w] : vec[u])
      |              ^
valley.cpp: In function 'int main()':
valley.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |         auto [u, v] = much[i];
      |              ^

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