Submission #915598

#	Time	Username	Problem	Language	Result	Execution time	Memory
915598		uped	Valley (BOI19_valley)	C++14	100 / 100	357 ms	68660 KiB

valley

#include <bits/stdc++.h>

#define DEBUG(x) cout << #x << ": " << x << '\n';

using namespace std;
using ll = long long;

const ll MAXN = 1e5 + 1;
const ll INF = 1e18;
vector<pair<ll, ll>> adj[MAXN];
ll shop_in_subtree[MAXN];
ll tin[MAXN];
ll tout[MAXN];
ll depth[MAXN];
// destination, min(shop_in_subtree) on path to dst, dist_of_path
tuple<ll, ll, ll> jmp[20][MAXN];
bool is_shop[MAXN];
ll timer = 0;

void dfs(ll n, ll p = 0, ll pw = 0) {
    depth[n] = depth[p] + 1;
    tin[n] = timer++;
    shop_in_subtree[n] = (is_shop[n] ? 0 : INF);
    for (auto& [x, w] : adj[n]) {
        if (x == p) continue;
        dfs(x, n, w);
        shop_in_subtree[n] = min(shop_in_subtree[x] + w, shop_in_subtree[n]);
    }
    jmp[0][n] = {p, shop_in_subtree[n], pw};
    tout[n] = timer++;
}

int main() {
    ll n, s, q, e;
    cin >> n >> s >> q >> e;
    vector<pair<ll, ll>> edges(n - 1);
    for (ll i = 0; i < n - 1; ++i) {
        ll a, b, w;
        cin >> a >> b >> w;
        adj[a].emplace_back(b, w);
        adj[b].emplace_back(a, w);
        edges[i] = {a, b};
    }

    for (ll i = 0; i < s; ++i) {
        ll x;
        cin >> x;
        is_shop[x] = true;
    }
    dfs(e);
    for (ll i = 1; i < 20; ++i) {
        for (ll j = 1; j <= n; ++j) {
            auto& [a, b, c] = jmp[i - 1][j];
            auto& [x, y, z] = jmp[i - 1][a];
            jmp[i][j] = {x, min(b, c + y), c + z};
        }
    }

    // for (ll i = 1; i <= n; ++i) {
    //     cout << jmp[0][i].second << ' ';
    // }
    // cout << '\n';

    for (ll i = 0; i < q; ++i) {
        ll idx, r;
        cin >> idx >> r;
        auto& [a, b] = edges[idx - 1];
        // a is deeper
        if (depth[b] > depth[a]) swap(a, b);
        if (tin[r] <= tout[a] && tin[r] >= tin[a]) {
            ll ans = shop_in_subtree[r];
            ll sum = 0;
            for (ll j = 19; j >= 0; --j) {
                auto& [x, y, z] = jmp[j][r];
                if (x != 0 && depth[x] >= depth[a]) {
                    ans = min(ans, y + sum);
                    r = x;
                    sum += z;
                }
            }
            ans = min(ans, shop_in_subtree[r] + sum);
            if (ans == INF) {
                cout << "oo\n";
            } else {
                cout << ans << '\n';
            }
        } else {
            cout << "escaped\n";
        }
    }
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(ll, ll, ll)':
valley.cpp:24:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |     for (auto& [x, w] : adj[n]) {
      |                ^
valley.cpp: In function 'int main()':
valley.cpp:53:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |             auto& [a, b, c] = jmp[i - 1][j];
      |                   ^
valley.cpp:54:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |             auto& [x, y, z] = jmp[i - 1][a];
      |                   ^
valley.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |         auto& [a, b] = edges[idx - 1];
      |               ^
valley.cpp:74:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |                 auto& [x, y, z] = jmp[j][r];
      |                       ^

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