Submission #1104695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104695		ShadowShark	Valley (BOI19_valley)	C++17	100 / 100	129 ms	40960 KiB

valley

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 5; const long long inf = 1e18;
long long dis[maxN], spec[maxN], jp[20][maxN];
int par[20][maxN], in[maxN], out[maxN], sus[maxN], pos[maxN], timeDfs = 0;
vector<pair<int, int>> adj[maxN];

struct tmp {
    int u, v, w;
} edge[maxN];

void dfs(int u, int pre) {
    in[u] = ++timeDfs;
    pos[timeDfs] = u;
    for (auto it: adj[u]) {
        int v = it.first, w = it.second;
        if (v == pre) continue;
        dis[v] = dis[u] + w;
        par[0][v] = u;
        dfs(v, u);
    }
    out[u] = timeDfs;
}

long long st[4 * maxN];
void build(int id, int l, int r) {
    if (l == r) {
        if (sus[pos[l]]) st[id] = dis[pos[l]];
            else st[id] = inf;
        return ;
    }

    int mid = (l + r) >> 1;

    build(2 * id, l, mid);
    build(2 * id + 1, mid + 1, r);

    st[id] = min(st[2 * id], st[2 * id + 1]);
}

long long get(int id, int l, int r, int u, int v) {
    if (v < l || r < u) return inf;
    if (u <= l && r <= v) return st[id];

    int mid = (l + r) >> 1;

    long long A = get(2 * id, l, mid, u, v);
    long long B = get(2 * id + 1, mid + 1, r, u, v);

    return min(A, B);
}

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

    int n, s, q, root;
    cin >> n >> s >> q >> root;

    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[i] = {u, v, w};

        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    for (int i = 1; i <= s; i++) {
        int x; cin >> x;
        sus[x] = 1;
    }

    dfs(root, root);
    build(1, 1, n);

    for (int i = 1; i <= n; i++) {
        spec[i] = inf;
        long long len = get(1, 1, n, in[i], out[i]);
        if (len != inf) spec[i] = len - dis[i] * 2;
    }

    for (int i = 1; i <= n; i++)
        jp[0][i] = spec[par[0][i]];

    for (int k = 1; k <= 16; k++) {
        for (int i = 1; i <= n; i++) {
            par[k][i] = par[k - 1][par[k - 1][i]];
            jp[k][i] = min(jp[k - 1][i], jp[k - 1][par[k - 1][i]]);
        }
    }

    for (int i = 1; i < n; i++)
        if (in[edge[i].u] > in[edge[i].v]) swap(edge[i].u, edge[i].v);

    while (q--) {
        int id, u;
        cin >> id >> u;

        int p = edge[id].v;
        if (!(in[p] <= in[u] && out[u] <= out[p])) {
            cout << "escaped\n";
            continue;
        }

        long long ans = inf, org = dis[u];
        ans = min(ans, spec[u]);

        for (int k = 16; k >= 0; k--) {
            int v = par[k][u];
            if (in[p] <= in[v]) {
                ans = min(ans, jp[k][u]);
                u = v;
            }
        }

        if (ans == inf) cout << "oo\n";
            else cout << ans + org << '\n';
    }

    return 0;
}

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