oj.uz

Submission #915420

# Submission time Handle Problem Language Result Execution time Memory
915420 2024-01-23T21:05:57 Z uped Valley (BOI19_valley) C++14
23 / 100
 353 ms 67412 KB 
#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];
// 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) {
    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];
        ll in = max(tin[a], tin[b]);
        ll out = min(tout[a], tout[b]);
        if (tin[r] <= out && tin[r] >= in) {
            ll ans = shop_in_subtree[r];
            ll sum = 0;
            for (ll j = 19; j >= 0; --j) {
                auto& [a, b, c] = jmp[j][r];
                if (a >= in) {
                    ans = min(ans, b + sum);
                    r = a;
                    sum += c;
                }
            }
            ans = min(ans, shop_in_subtree[r] + sum);
            if (ans == INF) {
                cout << "oo\n";
            } else {
                cout << ans << '\n';
            }
        } else {
            cout << "escaped\n";
        }
    }
}

Compilation message

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 45980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 45980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 63328 KB Output is correct
2 Correct 302 ms 63164 KB Output is correct
3 Correct 340 ms 63336 KB Output is correct
4 Correct 353 ms 65108 KB Output is correct
5 Correct 310 ms 65212 KB Output is correct
6 Correct 335 ms 67412 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 45980 KB Output isn't correct
2 Halted 0 ms 0 KB -