oj.uz

Submission #645607

# Submission time Handle Problem Language Result Execution time Memory
645607 2022-09-27T13:11:23 Z alextodoran Valley (BOI19_valley) C++17
100 / 100
 184 ms 38080 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int BITS = 17;
const ll INF = LLONG_MAX / 2;

int N, S, Q, E;
bool shop[N_MAX + 2];
struct Edge {
    int u, v;
    int len;
    int to (int x) {
        return u ^ v ^ x;
    }
};
Edge edges[N_MAX + 2];

vector <int> adj[N_MAX + 2];
int pedge[N_MAX + 2];

int level[N_MAX + 2];
ll depth[N_MAX + 2];
ll minDown[N_MAX + 2];

void dfs (int u) {
    if (shop[u] == true) {
        minDown[u] = 0;
    } else {
        minDown[u] = INF;
    }
    for (int e : adj[u]) {
        int v = edges[e].to(u);
        if (v != edges[pedge[u]].to(u)) {
            pedge[v] = e;
            level[v] = level[u] + 1;
            depth[v] = depth[u] + edges[e].len;
            dfs(v);
            minDown[u] = min(minDown[u], minDown[v] + edges[e].len);
        }
    }
}

int ancestor[N_MAX + 2][BITS];
ll minPath[N_MAX + 2][BITS];
void precalc () {
    minDown[0] = INF;
    for (int k = 0; k < BITS; k++) {
        minPath[0][k] = INF;
    }
    for (int u = 1; u <= N; u++) {
        int v = edges[pedge[u]].to(u);
        ancestor[u][0] = v;
        if (minDown[u] == INF) {
            minPath[u][0] = INF;
        } else {
            minPath[u][0] = minDown[u] - depth[u];
        }
        if (minDown[v] != INF) {
            minPath[u][0] = min(minPath[u][0], minDown[v] - depth[v]);
        }
    }
    for (int k = 1; k < BITS; k++) {
        for (int u = 1; u <= N; u++) {
            ancestor[u][k] = ancestor[ancestor[u][k - 1]][k - 1];
            minPath[u][k] = min(minPath[u][k - 1], minPath[ancestor[u][k - 1]][k - 1]);
        }
    }
}

pair <int, ll> goUp (int u, int len) {
    ll mn = INF;
    if (minDown[u] != INF) {
        mn = minDown[u] - depth[u];
    }
    for (int k = 0; k < BITS; k++) {
        if ((len >> k) & 1) {
            mn = min(mn, minPath[u][k]);
            u = ancestor[u][k];
        }
    }
    return make_pair(u, mn);
}

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

    cin >> N >> S >> Q >> E;
    for (int e = 1; e <= N - 1; e++) {
        cin >> edges[e].u >> edges[e].v >> edges[e].len;
        adj[edges[e].u].push_back(e);
        adj[edges[e].v].push_back(e);
    }
    for (int i = 1; i <= S; i++) {
        int u;
        cin >> u;
        shop[u] = true;
    }

    dfs(E);
    precalc();

    for (int i = 1; i <= Q; i++) {
        int e, u;
        cin >> e >> u;
        int v = edges[e].u;
        if (level[v] < level[edges[e].v]) {
            v = edges[e].v;
        }
        if (level[v] > level[u]) {
            cout << "escaped\n";
            continue;
        }
        int x; ll mn;
        tie(x, mn) = goUp(u, level[u] - level[v]);
        if (x != v) {
            cout << "escaped\n";
            continue;
        }
        if (mn == INF) {
            cout << "oo\n";
        } else {
            cout << depth[u] + mn << "\n";
        }
    }

    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 5 ms 2772 KB Output is correct
4 Correct 4 ms 2772 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 3 ms 2772 KB Output is correct
3 Correct 5 ms 2772 KB Output is correct
4 Correct 4 ms 2772 KB Output is correct
5 Correct 4 ms 3028 KB Output is correct
6 Correct 3 ms 3000 KB Output is correct
7 Correct 3 ms 3028 KB Output is correct
8 Correct 3 ms 2944 KB Output is correct
9 Correct 2 ms 2900 KB Output is correct
10 Correct 3 ms 3028 KB Output is correct
11 Correct 2 ms 2996 KB Output is correct
12 Correct 3 ms 3000 KB Output is correct
13 Correct 4 ms 2948 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 125 ms 30156 KB Output is correct
2 Correct 133 ms 29900 KB Output is correct
3 Correct 145 ms 29892 KB Output is correct
4 Correct 154 ms 31656 KB Output is correct
5 Correct 158 ms 31788 KB Output is correct
6 Correct 184 ms 33924 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 3 ms 2772 KB Output is correct
3 Correct 5 ms 2772 KB Output is correct
4 Correct 4 ms 2772 KB Output is correct
5 Correct 4 ms 3028 KB Output is correct
6 Correct 3 ms 3000 KB Output is correct
7 Correct 3 ms 3028 KB Output is correct
8 Correct 3 ms 2944 KB Output is correct
9 Correct 2 ms 2900 KB Output is correct
10 Correct 3 ms 3028 KB Output is correct
11 Correct 2 ms 2996 KB Output is correct
12 Correct 3 ms 3000 KB Output is correct
13 Correct 4 ms 2948 KB Output is correct
14 Correct 3 ms 3028 KB Output is correct
15 Correct 125 ms 30156 KB Output is correct
16 Correct 133 ms 29900 KB Output is correct
17 Correct 145 ms 29892 KB Output is correct
18 Correct 154 ms 31656 KB Output is correct
19 Correct 158 ms 31788 KB Output is correct
20 Correct 184 ms 33924 KB Output is correct
21 Correct 117 ms 33352 KB Output is correct
22 Correct 117 ms 33100 KB Output is correct
23 Correct 142 ms 33076 KB Output is correct
24 Correct 152 ms 35100 KB Output is correct
25 Correct 179 ms 38028 KB Output is correct
26 Correct 115 ms 33440 KB Output is correct
27 Correct 130 ms 33228 KB Output is correct
28 Correct 147 ms 33360 KB Output is correct
29 Correct 144 ms 34588 KB Output is correct
30 Correct 177 ms 36212 KB Output is correct
31 Correct 130 ms 33528 KB Output is correct
32 Correct 122 ms 33396 KB Output is correct
33 Correct 138 ms 33304 KB Output is correct
34 Correct 177 ms 35256 KB Output is correct
35 Correct 163 ms 38080 KB Output is correct
36 Correct 145 ms 35044 KB Output is correct