Submission #1282187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282187		hanguyendanghuy	Valley (BOI19_valley)	C++20	59 / 100	3066 ms	21840 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
const ll MAXN = 4e5 + 5, INF = 1e18, MOD = 1e9 + 7, MAXV = 4e5 + 2;
ll n, m, i, j, k, p, dem, cnt, ans, S, Q, root, dtr[MAXN], shop[MAXN], mark[MAXN], preshop[MAXN], par[MAXN], dist[MAXN], chain[MAXN], headchain[MAXN], st[MAXN], en[MAXN], cntchain = 1, de[MAXN], sz[MAXN];
vector<pair<ll, ll>> adj[MAXN];
pair<ll, ll> edge[MAXN];

ll dfs(ll st) {
    sz[st] = 1;
    if (shop[st] & 1) preshop[st] = st;
    ll best = INF;
    for (auto x : adj[st]) {
        if (de[x.fi]) continue;
        de[x.fi] = de[st] + 1;
        dtr[x.fi] = dtr[st] + x.se;
        par[x.fi] = st;
        preshop[x.fi] = preshop[st];
        best = min(best, dfs(x.fi) + x.se);
        sz[st] += sz[x.fi];
    }
    if (shop[st] & 1) best = 0;
    dist[st] = best;
    return best;
}

void HLD(ll u) {
    if (!headchain[cntchain]) headchain[cntchain] = u;
    chain[u] = cntchain;
    ll v = -1, maxsz = -1;
    for (auto x : adj[u])
        if (x.fi != par[u] && sz[x.fi] > maxsz) maxsz = sz[x.fi], v = x.fi;
    if (v != -1) HLD(v);
    for (auto x : adj[u])
        if (x.fi != par[u] && x.fi != v) {
            ++cntchain;
            HLD(x.fi);
        }
    en[u] = cntchain;
}

ll lca(ll u, ll v) {
    while (chain[u] != chain[v]) {
        if (de[headchain[chain[u]]] > de[headchain[chain[v]]])
            u = par[headchain[chain[u]]];
        else
            v = par[headchain[chain[v]]];
    }
    return (de[u] < de[v] ? u : v);
}

ll tinh(ll u, ll v) {
    return de[u] + de[v] - 2 * de[lca(u, v)];
}

void check(ll u, ll st) {
    ll stchain = chain[u], enchain = en[u], cur = preshop[st];
    if (cur > 0 && de[cur] >= de[u]) ans = min(ans, dtr[st] - dtr[cur]);
    for (ll i = stchain; i <= enchain; i++) {
        ll pa = par[headchain[i]];
        if (!pa || de[pa] < de[u]) continue;
        ans = min(ans, dist[pa] + dtr[pa] + dtr[st] - 2 * dtr[lca(st, pa)]);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> S >> Q >> root;
    for (i = 1; i < n; i++) {
        ll u, v, c;
        cin >> u >> v >> c;
        edge[i] = {u, v};
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }
    for (i = 1; i <= S; i++) cin >> k, shop[k] = 1;
    de[root] = 1;
    fill(dist + 1, dist + n + 1, INF);
    dfs(root);
    HLD(root);
    for (i = 1; i <= Q; i++) {
        ll block, E;
        cin >> block >> E;
        ll u = edge[block].fi, v = edge[block].se;
        if (de[u] < de[v]) swap(u, v);
        ans = INF;
        if (tinh(u, E) + tinh(v, root) + 1 == tinh(E, root)) {
            ans = min(ans, dist[E]);
            ans = min(ans, dist[u] - dtr[u] + dtr[E]);
            check(u, E);
            if (ans >= INF)
                cout << "oo\n";
            else
                cout << ans << '\n';
        } else
            cout << "escaped\n";
    }
}

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