Submission #1280361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280361		Aquarius	Valley (BOI19_valley)	C++20	0 / 100	46 ms	15068 KiB

valley

#include<bits/stdc++.h>
#define int long long
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

struct Edge{
    int u, v, w;
};

const int INF  = 1e15;

const int N = 1e5+5;
Edge edges[N];
vector<pair<int,int>> E[N];


int par[20][N], val[20][N];
int dist[N], dep[N];

int st[N], ed[N];

bool shop[N];

int n, s, q, root, t = 0;

int dfs(int u, int p) {
    dist[u] += dist[p];
    dep[u] = dep[p] + 1;
    par[0][u] = p;

    st[u] = ++t;

    int res = INF;

    for(auto [v, w]: E[u]) {
        if(v == p) continue;
        dist[v] = w;
        res = min(res, dfs(v, u));
    }

    ed[u] = t;

    if(shop[u]) res = min(res, dist[u]);
    if(res!= INF) val[0][u] = res - 2*dist[u];
    else val[0][u] = INF;
    return res;
}


void build() {
    for(int k=1; k<20; k++) {
        for(int i=1; i<=n; i++) {
            par[k][i] = par[k-1][par[k-1][i]];
            val[k][i] = min(val[k-1][i], val[k-1][par[i-1][i]]);
        }
    }
}


int find_val_min(int u, int p) {

    int d = dep[u] - dep[p];
    int res = INF;

    for(int k=0; k<20; k++) {
        if(d&(1<<k)) {
            res = min(res, val[k][u]);
            u = par[k][u];
        }
    }

    return min(res, val[0][u]);
}

bool is_ancestor(int u, int p) {
    return (st[p] <= st[u] && ed[u] <=ed[p]);
}

void solve() {
    cin >> n >> s >> q >> root;
    for(int i=1; i<n; i++) {
        int u, v, w; cin >> u >> v >> w;
        E[u].push_back({v, w});
        E[v].push_back({u, w});
        edges[i] = {u, v, w};
    }
    for(int i=1; i<=s; i++) {
        int u; cin >> u ;
        shop[u] = true;
    }

    dfs(root, 0);
    build();




    while(q--) {
        int id, x; cin >> id >> x;
        auto[u, v, w] = edges[id];
        if(dep[u] < dep[v]) swap(u, v);

        if(!is_ancestor(x, u)) cout<<"escaped\n";
        else {
            int res = find_val_min(x, u);
            if(res == INF) cout<<"oo\n";
            else {
                cout<< dist[x] + res <<'\n';
            }
        }

    }

}

signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int T = 1;
//    cin >> T;
    while(T--) solve();
}

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