Submission #703616

#	Time	Username	Problem	Language	Result	Execution time	Memory
703616		bebra	Valley (BOI19_valley)	C++17	59 / 100	216 ms	79620 KiB

valley

#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});
            } else {
                ans = min_dist[r];
            }
        }

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

    return 0;
}


/*
10 1 1 7
1 2 10
2 3 9
3 8 5
2 4 3
2 5 9
5 6 1
6 7 10
5 9 10
5 10 5

7

7 8
*/

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41