oj.uz

Submission #481254

# Submission time Handle Problem Language Result Execution time Memory
481254 2021-10-20T05:53:16 Z schiftyfive4 Valley (BOI19_valley) C++14
100 / 100
 310 ms 56636 KB 
#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int N = 100000;
const i64 inf = 1e18;
int n, s, q, E, t = 0;

vector<i64> in(N), out(N), shop(N), x(N, inf), dp(N), d(N);
vector<pair<int, int>> e;
vector<vector<pair<int, int>>> g(N);
vector<vector<i64>> go(N, vector<i64>(18)), mn(N, vector<i64>(18));

void dfs(int u, int p) {
    in[u] = t++;
    go[u][0] = p;
    if (shop[u]) {
        x[u] = d[u];
    }
    for (auto [v, w] : g[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::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> s >> q >> E;
    --E;

    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        e.emplace_back(u, v);
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

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

    dfs(E, E);

    for (int b = 1; b < 18; b++) {
        for (int i = 0; i < n; i++) {
            go[i][b] = go[go[i][b - 1]][b - 1];
            mn[i][b] = min(mn[i][b - 1], mn[go[i][b - 1]][b - 1]);
        }
    }

    while (q--) {
        int i, r;
        cin >> i >> r;
        --i; --r;
        auto [u, v] = e[i];
        if (is_ancestor(u, v)) {
            swap(u, v);
        }
        if (!is_ancestor(u, r)) {
            cout << "escaped\n";
        } else {
            i64 best = dp[u], dd = d[r];
            for (int b = 17; b >= 0; b--) {
                if (is_ancestor(u, go[r][b])) {
                    best = min(best, mn[r][b]);
                    r = go[r][b];
                }
            }
            if (best == inf) {
                cout << "oo\n";
            } else {
                cout << dd + best << '\n';
            }
        }
    }

}

Compilation message

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:21:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for (auto [v, w] : g[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] = e[i];
      |              ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 43384 KB Output is correct
2 Correct 32 ms 43412 KB Output is correct
3 Correct 33 ms 43512 KB Output is correct
4 Correct 33 ms 43496 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 43384 KB Output is correct
2 Correct 32 ms 43412 KB Output is correct
3 Correct 33 ms 43512 KB Output is correct
4 Correct 33 ms 43496 KB Output is correct
5 Correct 28 ms 43372 KB Output is correct
6 Correct 32 ms 43416 KB Output is correct
7 Correct 29 ms 43396 KB Output is correct
8 Correct 29 ms 43424 KB Output is correct
9 Correct 31 ms 43468 KB Output is correct
10 Correct 32 ms 43404 KB Output is correct
11 Correct 29 ms 43376 KB Output is correct
12 Correct 32 ms 43356 KB Output is correct
13 Correct 37 ms 43400 KB Output is correct
14 Correct 33 ms 43492 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 48704 KB Output is correct
2 Correct 232 ms 52252 KB Output is correct
3 Correct 261 ms 52200 KB Output is correct
4 Correct 284 ms 53864 KB Output is correct
5 Correct 260 ms 54120 KB Output is correct
6 Correct 300 ms 55912 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 43384 KB Output is correct
2 Correct 32 ms 43412 KB Output is correct
3 Correct 33 ms 43512 KB Output is correct
4 Correct 33 ms 43496 KB Output is correct
5 Correct 28 ms 43372 KB Output is correct
6 Correct 32 ms 43416 KB Output is correct
7 Correct 29 ms 43396 KB Output is correct
8 Correct 29 ms 43424 KB Output is correct
9 Correct 31 ms 43468 KB Output is correct
10 Correct 32 ms 43404 KB Output is correct
11 Correct 29 ms 43376 KB Output is correct
12 Correct 32 ms 43356 KB Output is correct
13 Correct 37 ms 43400 KB Output is correct
14 Correct 33 ms 43492 KB Output is correct
15 Correct 217 ms 48704 KB Output is correct
16 Correct 232 ms 52252 KB Output is correct
17 Correct 261 ms 52200 KB Output is correct
18 Correct 284 ms 53864 KB Output is correct
19 Correct 260 ms 54120 KB Output is correct
20 Correct 300 ms 55912 KB Output is correct
21 Correct 249 ms 52000 KB Output is correct
22 Correct 215 ms 51712 KB Output is correct
23 Correct 232 ms 51776 KB Output is correct
24 Correct 296 ms 53632 KB Output is correct
25 Correct 271 ms 56636 KB Output is correct
26 Correct 204 ms 51972 KB Output is correct
27 Correct 219 ms 51736 KB Output is correct
28 Correct 261 ms 51588 KB Output is correct
29 Correct 297 ms 52980 KB Output is correct
30 Correct 310 ms 54476 KB Output is correct
31 Correct 206 ms 52036 KB Output is correct
32 Correct 211 ms 51716 KB Output is correct
33 Correct 229 ms 51912 KB Output is correct
34 Correct 301 ms 53544 KB Output is correct
35 Correct 278 ms 56304 KB Output is correct
36 Correct 292 ms 53836 KB Output is correct