oj.uz

Submission #558337

# Submission time Handle Problem Language Result Execution time Memory
558337 2022-05-07T06:19:52 Z MayankGusain Valley (BOI19_valley) C++17
100 / 100
 665 ms 59224 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

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

vector<int> inTime(N), outTime(N), shop(N), shopDistanceToE(N, OO), distanceToShop(N), distanceToE(N);
vector<pair<int, int>> e;
vector<vector<pair<int, int>>> g(N);
vector<vector<int>> binaryJumpVertex(N, vector<int>(18)), mn(N, vector<int>(18));

void dfs(int u, int p) {
    inTime[u] = t++;
    binaryJumpVertex[u][0] = p;
    if (shop[u]) {
        shopDistanceToE[u] = distanceToE[u];
    }
 
    for (auto [v, w] : g[u])  { 
        if (v != p) {
            distanceToE[v] = distanceToE[u] + w;
            dfs(v, u);
            shopDistanceToE[u] = min(shopDistanceToE[u], shopDistanceToE[v]);
        }
    }
 
    distanceToShop[u] = (shopDistanceToE[u] == OO ? OO : shopDistanceToE[u] - 2 * distanceToE[u]);
    mn[u][0] = distanceToShop[u];
    outTime[u] = t++;
}

bool is_ancestor(int u, int v) {
    return (inTime[u] <= inTime[v] && outTime[v] <= outTime[u]);
}

signed main() {
    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++) {
            binaryJumpVertex[i][b] = binaryJumpVertex[binaryJumpVertex[i][b - 1]][b - 1];
            mn[i][b] = min(mn[i][b - 1], mn[binaryJumpVertex[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 {
            int best = distanceToShop[u], distanceRE = distanceToE[r];
            for (int b = 17; b >= 0; b--) {
                if (is_ancestor(u, binaryJumpVertex[r][b])) {
                    best = min(best, mn[r][b]);
                    r = binaryJumpVertex[r][b];
                }
            }
 
            if (best == OO) {
                cout << "oo\n";
            } else {
                cout << distanceRE + best << '\n';
            }
        }
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 43464 KB Output is correct
2 Correct 51 ms 43504 KB Output is correct
3 Correct 61 ms 43492 KB Output is correct
4 Correct 59 ms 43512 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 43464 KB Output is correct
2 Correct 51 ms 43504 KB Output is correct
3 Correct 61 ms 43492 KB Output is correct
4 Correct 59 ms 43512 KB Output is correct
5 Correct 39 ms 43472 KB Output is correct
6 Correct 34 ms 43380 KB Output is correct
7 Correct 40 ms 43388 KB Output is correct
8 Correct 33 ms 43384 KB Output is correct
9 Correct 34 ms 43464 KB Output is correct
10 Correct 34 ms 43364 KB Output is correct
11 Correct 32 ms 43424 KB Output is correct
12 Correct 32 ms 43356 KB Output is correct
13 Correct 33 ms 43444 KB Output is correct
14 Correct 34 ms 43384 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 54604 KB Output is correct
2 Correct 518 ms 54404 KB Output is correct
3 Correct 506 ms 54796 KB Output is correct
4 Correct 632 ms 56500 KB Output is correct
5 Correct 508 ms 56616 KB Output is correct
6 Correct 665 ms 58768 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 43464 KB Output is correct
2 Correct 51 ms 43504 KB Output is correct
3 Correct 61 ms 43492 KB Output is correct
4 Correct 59 ms 43512 KB Output is correct
5 Correct 39 ms 43472 KB Output is correct
6 Correct 34 ms 43380 KB Output is correct
7 Correct 40 ms 43388 KB Output is correct
8 Correct 33 ms 43384 KB Output is correct
9 Correct 34 ms 43464 KB Output is correct
10 Correct 34 ms 43364 KB Output is correct
11 Correct 32 ms 43424 KB Output is correct
12 Correct 32 ms 43356 KB Output is correct
13 Correct 33 ms 43444 KB Output is correct
14 Correct 34 ms 43384 KB Output is correct
15 Correct 504 ms 54604 KB Output is correct
16 Correct 518 ms 54404 KB Output is correct
17 Correct 506 ms 54796 KB Output is correct
18 Correct 632 ms 56500 KB Output is correct
19 Correct 508 ms 56616 KB Output is correct
20 Correct 665 ms 58768 KB Output is correct
21 Correct 442 ms 54020 KB Output is correct
22 Correct 486 ms 53772 KB Output is correct
23 Correct 541 ms 53988 KB Output is correct
24 Correct 601 ms 56300 KB Output is correct
25 Correct 604 ms 59224 KB Output is correct
26 Correct 530 ms 54048 KB Output is correct
27 Correct 509 ms 53900 KB Output is correct
28 Correct 494 ms 54104 KB Output is correct
29 Correct 590 ms 55580 KB Output is correct
30 Correct 574 ms 57128 KB Output is correct
31 Correct 460 ms 54128 KB Output is correct
32 Correct 485 ms 54052 KB Output is correct
33 Correct 551 ms 54240 KB Output is correct
34 Correct 586 ms 56120 KB Output is correct
35 Correct 531 ms 59180 KB Output is correct
36 Correct 528 ms 56044 KB Output is correct