Submission #547578

#	Time	Username	Problem	Language	Result	Execution time	Memory
547578		Jomnoi	Valley (BOI19_valley)	C++17	100 / 100	337 ms	29688 KiB

valley

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

const int MAX_N = 1e5 + 10;
const long long INF = 1e18 + 7;

int A[MAX_N], B[MAX_N], W[MAX_N];
vector <pair <int, int>> graph[MAX_N];
long long dist[MAX_N];

// Heavy Light Decomposition
int timer;
int sz[MAX_N], depth[MAX_N], parent[MAX_N][20];
int head[MAX_N], st[MAX_N], pos[MAX_N];

// Segment Tree
long long tree[4 * MAX_N];

int get_size(const int &u, const int &p) {
    sz[u] = 1;
    for(int i = 1; i < 20; i++) {
        parent[u][i] = parent[parent[u][i - 1]][i - 1];
    }
    for(auto [v, w] : graph[u]) {
        if(v == p) {
            continue;
        }

        depth[v] = depth[u] + 1;
        parent[v][0] = u;
        dist[v] = dist[u] + w;
        sz[u] += get_size(v, u);
    }
    return sz[u];
}

void build_hld(const int &u, const int &p, const int &t) {
    timer++;
    head[u] = t;
    st[u] = timer;
    pos[timer] = u;

    int max_size = 0, biggest = -1;
    for(auto [v, w] : graph[u]) {
        if(v != p and max_size < sz[v]) {
            max_size = sz[v];
            biggest = v;
        }
    }

    if(biggest != -1) {
        build_hld(biggest, u, t);
    }
    for(auto [v, w] : graph[u]) {
        if(v != p and v != biggest) {
            build_hld(v, u, v);
        }
    }
}

int find_lca(const int &a, const int &b) {
    int u = a, v = b;
    if(depth[u] < depth[v]) {
        swap(u, v);
    }
    for(int i = 19; i >= 0; i--) {
        if(depth[parent[u][i]] >= depth[v]) {
            u = parent[u][i];
        }
    }
    for(int i = 19; i >= 0; i--) {
        if(parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return (u == v ? u : parent[u][0]);
}

void build_seg(const int &idx, const int &l, const int &r) {
    tree[idx] = INF;
    if(l == r) {
        return;
    }

    int mid = (l + r) / 2;
    build_seg(idx * 2, l, mid);
    build_seg(idx * 2 + 1, mid + 1, r);
}

void update(const int &idx, const int &l, const int &r, const int &ql, const int &qr, const long long &v) {
    if(r < ql or qr < l) {
        return;
    }
    if(ql <= l and r <= qr) {
        tree[idx] = min(tree[idx], v);
        return;
    }

    int mid = (l + r) / 2;
    update(idx * 2, l, mid, ql, qr, v);
    update(idx * 2 + 1, mid + 1, r, ql, qr, v);
}

void construct(const int &idx, const int &l, const int &r) {
    if(l == r) {
        if(tree[idx] != INF) {
            tree[idx] -= 2 * dist[pos[l]];
        }
        return;
    }

    tree[idx * 2] = min(tree[idx * 2], tree[idx]);
    tree[idx * 2 + 1] = min(tree[idx * 2 + 1], tree[idx]);

    int mid = (l + r) / 2;
    construct(idx * 2, l, mid);
    construct(idx * 2 + 1, mid + 1, r);
    tree[idx] = min(tree[idx * 2], tree[idx * 2 + 1]);
}

long long query(int idx, int l, int r, int ql, int qr) {
    if(r < ql or qr < l) {
        return INF;
    }
    if(ql <= l and r <= qr) {
        return tree[idx];
    }

    int mid = (l + r) / 2;
    return min(query(idx * 2, l, mid, ql, qr), query(idx * 2 + 1, mid + 1, r, ql, qr));
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N, S, Q, E;
    cin >> N >> S >> Q >> E;
    for(int i = 1; i <= N - 1; i++) {
        cin >> A[i] >> B[i] >> W[i];
        graph[A[i]].emplace_back(B[i], W[i]);
        graph[B[i]].emplace_back(A[i], W[i]);
    }

    depth[0] = -1;
    get_size(E, -1);
    build_hld(E, -1, E);
    build_seg(1, 1, N);

    for(int i = 1; i <= S; i++) {
        int C;
        cin >> C;

        int u = C;
        while(true) {
            if(head[E] == head[u]) {
                update(1, 1, N, st[E], st[u], dist[C]);
                break;
            }

            update(1, 1, N, st[head[u]], st[u], dist[C]);
            u = parent[head[u]][0];
        }
    }

    construct(1, 1, N);

    for(int i = 1; i <= N - 1; i++) {
        if(depth[A[i]] > depth[B[i]]) {
            swap(A[i], B[i]);
        }
    }

    for(int i = 1; i <= Q; i++) {
        int I, R;
        cin >> I >> R;

        int lca = find_lca(B[I], R);
        if(lca != B[I]) {
            cout << "escaped\n";
            continue;
        }

        int u = R;
        long long res = INF;
        while(true) {
            if(head[lca] == head[u]) {
                res = min(res, query(1, 1, N, st[lca], st[u]));
                break;
            }

            res = min(res, query(1, 1, N, st[head[u]], st[u]));
            u = parent[head[u]][0];
        }

        if(res != INF) {
            cout << res + dist[R] << '\n';
        }
        else {
            cout << "oo\n";
        }
    }
    return 0;
}

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