oj.uz

Submission #703621

# Submission time Handle Problem Language Result Execution time Memory
703621 2023-02-27T19:23:48 Z bebra Valley (BOI19_valley) C++17
100 / 100
 217 ms 79340 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define int long long

#define dbg(x) cerr << #x << ": " << x << endl;


const int MAX_N = 1e5 + 5;
const ll INF = 1e17;
vector<pair<int, ll>> g[MAX_N];
bool special[MAX_N];
pair<int, int> edges[MAX_N];


int tin[MAX_N];
int tout[MAX_N];
int timer = 0;

ll depth[MAX_N];
ll first_down_dist[MAX_N];
// from different subtree
ll second_down_dist[MAX_N];

const int MAX_K = 20;
int binup[MAX_K][MAX_N];
ll binup_first_dist[MAX_K][MAX_N];
ll binup_second_dist[MAX_K][MAX_N];

ll first_down_value[MAX_N];
ll second_down_value[MAX_N];



void dfs_down(int v, int p) {
    tin[v] = timer++;

    if (special[v]) {
        first_down_dist[v] = 0;
        second_down_dist[v] = 0;
    } else {
        first_down_dist[v] = INF;
        second_down_dist[v] = INF;
    }

    vector<ll> values;
    for (const auto& [u, w] : g[v]) {
        if (u == p) continue;
        depth[u] = depth[v] + w;
        binup[0][u] = v;
        dfs_down(u, v);
        values.emplace_back(first_down_dist[u] + w);
    }
    sort(values.begin(), values.end());
    if (values.size() == 1) {
        first_down_dist[v] = min(first_down_dist[v], values[0]);
    } else if (values.size() > 1) {
        first_down_dist[v] = min(first_down_dist[v], values[0]);
        second_down_dist[v] = min(second_down_dist[v], values[1]);
    }

    if (first_down_dist[v] != INF) {
        first_down_value[v] = first_down_dist[v] - depth[v];
    } else {
        first_down_value[v] = INF;
    }
    if (second_down_dist[v] != INF) {
        second_down_value[v] = second_down_dist[v] + depth[v];
    } else {
        second_down_value[v] = INF;
    }

    tout[v] = timer;
}


ll up_dist[MAX_N];
ll min_dist[MAX_N];

void dfs_up(int v) {
    for (const auto& [u, w] : g[v]) {
        g[u].erase(find(g[u].begin(), g[u].end(), make_pair(v, w)));
    }
    if (special[v]) {
        up_dist[v] = 0;
    }
    int n = g[v].size();
    vector<ll> pref_min(n + 1, INF);
    vector<ll> suf_min(n + 1, INF);
    for (int i = 0; i < n; ++i) {
        auto [u, w] = g[v][i];
        pref_min[i + 1] = min(pref_min[i], first_down_dist[u] + w);
    }
    for (int i = n - 1; i >= 0; --i) {
        auto [u, w] = g[v][i];
        suf_min[i] = min(suf_min[i + 1], first_down_dist[u] + w);
    }
    min_dist[v] = min(up_dist[v], first_down_dist[v]);
    for (int i = 0; i < n; ++i) {
        auto [u, w] = g[v][i];
        up_dist[u] = min({up_dist[v], pref_min[i], suf_min[i + 1]}) + w;
        dfs_up(u);
    }
}


bool is_parent(int p, int v) {
    return tin[p] <= tin[v] && tout[v] <= tout[p];
}

int get_lca(int u, int v) {
    if (is_parent(u, v)) return u;
    if (is_parent(v, u)) return v;

    for (int k = MAX_K - 1; k >= 0; --k) {
        if (!is_parent(binup[k][v], u)) {
            v = binup[k][v];
        }
    }
    return binup[0][v];
}

ll get_dist(int u, int v) {
    int lca = get_lca(u, v);
    return depth[u] + depth[v] - 2 * depth[lca];
}

ll get_second_dist(int u, int v) {
    // min over second_down_dist[c] + depth[c] over all vertices c in path from v to u
    if (u == v) return second_down_value[v];
    if (!is_parent(u, v)) swap(u, v);

    ll res = INF;
    for (int k = MAX_K - 1; k >= 0; --k) {
        if (!is_parent(binup[k][v], u)) {
            res = min(res, binup_second_dist[k][v]);
            v = binup[k][v];
        }
    }
    res = min(res, binup_second_dist[0][v]);
    return res;
}

ll get_first_dist(int u, int v, bool f = false) {
    // min over first_down_dist[c] - depth[c] over all vertices c in path from v to u
    if (u == v) return first_down_value[v];
    if (!is_parent(u, v)) swap(u, v);

    ll res = INF;
    for (int k = MAX_K - 1; k >= 0; --k) {
        if (!is_parent(binup[k][v], u)) {
            res = min(res, binup_first_dist[k][v]);
            v = binup[k][v];
        }
    }

    if (!f) {
        res = min(res, binup_first_dist[0][v]);
    }
    return res;
}



int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, s, q, t;
    cin >> n >> s >> q >> t;
    --t;

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

    for (int i = 0; i < s; ++i) {
        int v;
        cin >> v;
        --v;
        special[v] = true;
    }


    dfs_down(0, -1);

    up_dist[0] = INF;
    dfs_up(0);

    for (int i = 0; i < n - 1; ++i) {
        auto& [u, v] = edges[i];
        if (!is_parent(u, v)) {
            swap(u, v);
        }
    }

    for (int v = 0; v < n; ++v) {
        binup_first_dist[0][v] = min(first_down_value[v], first_down_value[binup[0][v]]);
        binup_second_dist[0][v] = min(second_down_value[v], second_down_value[binup[0][v]]);
    }

    for (int k = 1; k < MAX_K; ++k) {
        for (int v = 0; v < n; ++v) {
            binup[k][v] = binup[k - 1][binup[k - 1][v]];
            binup_first_dist[k][v] = min(binup_first_dist[k - 1][v], binup_first_dist[k - 1][binup[k - 1][v]]);
            binup_second_dist[k][v] = min(binup_second_dist[k - 1][v], binup_second_dist[k - 1][binup[k - 1][v]]);
        }
    }

    while (q--) {
        int edge, r;
        cin >> edge >> r;
        --edge, --r;
        auto [u, v] = edges[edge];

        if ((is_parent(v, r) && is_parent(v, t)) || (!is_parent(v, r) && !is_parent(v, t))) {
            cout << "escaped\n";
            continue;
        }

        if (special[r]) {
            cout << "0\n";
            continue;
        }

        ll ans = INF;
        if (is_parent(r, u)) {
            if (get_dist(r, v) + first_down_dist[v] > min_dist[r]) {
                ans = min_dist[r];
            } else {
                ll value = get_second_dist(r, u);
                if (value != INF) value -= depth[r];
                ans = min(up_dist[r], value);
            }
        } else if (is_parent(v, r)) {
            if (get_dist(r, v) + up_dist[v] > min_dist[r]) {
                ans = min_dist[r];
            } else {
                ans = min(first_down_dist[r], get_first_dist(v, r) + depth[r]);
            }
        } else {
            if (get_dist(r, v) + first_down_dist[v] == min_dist[r]) {
                int lca = get_lca(r, u);

                ll value = get_second_dist(lca, u);
                if (value != INF) value += -2 * depth[lca] + depth[r];

                ans = min({first_down_dist[r], get_first_dist(r, lca, 1) + depth[r], value, up_dist[lca] + get_dist(lca, r)});
            } else {
                ans = min_dist[r];
            }
        }

        if (ans >= INF) {
            cout << "oo\n";
        } else {
            cout << ans << '\n';
        }
    }

    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3156 KB Output is correct
2 Correct 4 ms 3156 KB Output is correct
3 Correct 3 ms 3156 KB Output is correct
4 Correct 4 ms 3156 KB Output is correct
5 Correct 2 ms 3668 KB Output is correct
6 Correct 2 ms 3628 KB Output is correct
7 Correct 2 ms 3668 KB Output is correct
8 Correct 2 ms 3668 KB Output is correct
9 Correct 2 ms 3668 KB Output is correct
10 Correct 2 ms 3668 KB Output is correct
11 Correct 3 ms 3668 KB Output is correct
12 Correct 2 ms 3668 KB Output is correct
13 Correct 2 ms 3668 KB Output is correct
14 Correct 3 ms 3668 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 64188 KB Output is correct
2 Correct 135 ms 63960 KB Output is correct
3 Correct 146 ms 64232 KB Output is correct
4 Correct 155 ms 69156 KB Output is correct
5 Correct 154 ms 68232 KB Output is correct
6 Correct 165 ms 79340 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3156 KB Output is correct
2 Correct 4 ms 3156 KB Output is correct
3 Correct 3 ms 3156 KB Output is correct
4 Correct 4 ms 3156 KB Output is correct
5 Correct 2 ms 3668 KB Output is correct
6 Correct 2 ms 3628 KB Output is correct
7 Correct 2 ms 3668 KB Output is correct
8 Correct 2 ms 3668 KB Output is correct
9 Correct 2 ms 3668 KB Output is correct
10 Correct 2 ms 3668 KB Output is correct
11 Correct 3 ms 3668 KB Output is correct
12 Correct 2 ms 3668 KB Output is correct
13 Correct 2 ms 3668 KB Output is correct
14 Correct 3 ms 3668 KB Output is correct
15 Correct 148 ms 64188 KB Output is correct
16 Correct 135 ms 63960 KB Output is correct
17 Correct 146 ms 64232 KB Output is correct
18 Correct 155 ms 69156 KB Output is correct
19 Correct 154 ms 68232 KB Output is correct
20 Correct 165 ms 79340 KB Output is correct
21 Correct 131 ms 64052 KB Output is correct
22 Correct 146 ms 63868 KB Output is correct
23 Correct 157 ms 64172 KB Output is correct
24 Correct 210 ms 67412 KB Output is correct
25 Correct 165 ms 76236 KB Output is correct
26 Correct 126 ms 64208 KB Output is correct
27 Correct 149 ms 63992 KB Output is correct
28 Correct 161 ms 64236 KB Output is correct
29 Correct 192 ms 68620 KB Output is correct
30 Correct 194 ms 73356 KB Output is correct
31 Correct 128 ms 64204 KB Output is correct
32 Correct 152 ms 64076 KB Output is correct
33 Correct 154 ms 64348 KB Output is correct
34 Correct 180 ms 67704 KB Output is correct
35 Correct 186 ms 74872 KB Output is correct
36 Correct 217 ms 69668 KB Output is correct