oj.uz

Submission #559766

# Submission time Handle Problem Language Result Execution time Memory
559766 2022-05-10T14:26:27 Z hoanghq2004 Valley (BOI19_valley) C++14
100 / 100
 238 ms 41792 KB 
#include <bits/stdc++.h>

using namespace std;

int n, m, q, root;
int in[100010], out[100010], ti, s[100010];
int par[100010][20];
long long rmq[100010][20], d[100010], dmin[100010];
pair <int, int> e[100010];
vector <pair <int, int> > adj[100010];

void dfs(int u, int p) {
    in[u] = ++ti;
    dmin[u] = (s[u] ? d[u] : 1e18);
    par[u][0] = p;
    for (int i = 1; i < 20; ++i)
        par[u][i] = par[par[u][i - 1]][i - 1];
    for (auto [v, w]: adj[u]) {
        if (v == p) continue;
        d[v] = d[u] + w;
        dfs(v, u);
        dmin[u] = min(dmin[u], dmin[v]);
    }
    out[u] = ti;
}

void initrmq(int u, int p) {
    rmq[u][0] = dmin[u] - 2 * d[u];
    for (int i = 1; i < 20; ++i)
        rmq[u][i] = min(rmq[u][i - 1], rmq[par[u][i - 1]][i - 1]);
    for (auto [v, w]: adj[u]) {
        if (v == p) continue;
        initrmq(v, u);
    }
}

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

long long get(int u, int w) {
    long long res = rmq[w][0];
    for (int i = 19; i >= 0; --i) {
        if (par[u][i] && check(w, par[u][i])) {
            res = min(res, rmq[u][i]);
            u = par[u][i];
        }
    }
    return res;
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> q >> root;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        e[i] = {u, v};
    }
    while (m--) {
        int u;
        cin >> u;
        s[u] = 1;
    }
    dfs(root, 0);
    initrmq(root, 0);
    while (q--) {
        int u, id;
        cin >> id >> u;
        int w = (check(e[id].first, e[id].second) ? e[id].second : e[id].first);
        if (!check(w, u)) cout << "escaped\n";
        else {
            long long ans = get(u, w);
            if (ans >= 1e16) cout << "oo\n";
            else cout << ans + d[u] << "\n";
        }
    }
}

Compilation message

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:18:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for (auto [v, w]: adj[u]) {
      |               ^
valley.cpp: In function 'void initrmq(int, int)':
valley.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for (auto [v, w]: adj[u]) {
      |               ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 5 ms 2772 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct
4 Correct 4 ms 2820 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 5 ms 2772 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct
4 Correct 4 ms 2820 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct
6 Correct 3 ms 3028 KB Output is correct
7 Correct 3 ms 2992 KB Output is correct
8 Correct 3 ms 3028 KB Output is correct
9 Correct 3 ms 3028 KB Output is correct
10 Correct 3 ms 2948 KB Output is correct
11 Correct 4 ms 3028 KB Output is correct
12 Correct 3 ms 2948 KB Output is correct
13 Correct 3 ms 3028 KB Output is correct
14 Correct 3 ms 3028 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 38004 KB Output is correct
2 Correct 182 ms 37704 KB Output is correct
3 Correct 174 ms 37692 KB Output is correct
4 Correct 216 ms 39428 KB Output is correct
5 Correct 167 ms 39580 KB Output is correct
6 Correct 238 ms 41332 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 5 ms 2772 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct
4 Correct 4 ms 2820 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct
6 Correct 3 ms 3028 KB Output is correct
7 Correct 3 ms 2992 KB Output is correct
8 Correct 3 ms 3028 KB Output is correct
9 Correct 3 ms 3028 KB Output is correct
10 Correct 3 ms 2948 KB Output is correct
11 Correct 4 ms 3028 KB Output is correct
12 Correct 3 ms 2948 KB Output is correct
13 Correct 3 ms 3028 KB Output is correct
14 Correct 3 ms 3028 KB Output is correct
15 Correct 172 ms 38004 KB Output is correct
16 Correct 182 ms 37704 KB Output is correct
17 Correct 174 ms 37692 KB Output is correct
18 Correct 216 ms 39428 KB Output is correct
19 Correct 167 ms 39580 KB Output is correct
20 Correct 238 ms 41332 KB Output is correct
21 Correct 156 ms 37148 KB Output is correct
22 Correct 189 ms 36836 KB Output is correct
23 Correct 177 ms 36732 KB Output is correct
24 Correct 185 ms 38728 KB Output is correct
25 Correct 214 ms 41524 KB Output is correct
26 Correct 141 ms 37356 KB Output is correct
27 Correct 170 ms 37044 KB Output is correct
28 Correct 178 ms 37036 KB Output is correct
29 Correct 199 ms 38400 KB Output is correct
30 Correct 235 ms 39884 KB Output is correct
31 Correct 142 ms 37536 KB Output is correct
32 Correct 159 ms 37236 KB Output is correct
33 Correct 185 ms 37280 KB Output is correct
34 Correct 198 ms 39044 KB Output is correct
35 Correct 206 ms 41792 KB Output is correct
36 Correct 175 ms 39380 KB Output is correct