Submission #558625

#	Time	Username	Problem	Language	Result	Execution time	Memory
558625		Sorting	Valley (BOI19_valley)	C++17	100 / 100	264 ms	51720 KiB

valley

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const ll INF = 1e18;
const ll N = 1e5 + 3;
const ll MX = 1e15;
const int LOGN = 20;

int n, s, q, e;
vector<pair<int, ll>> adj[N];
bool shop[N];

int d[N], par[N];
ll up[LOGN][N], min_up[LOGN][N], mdist[N];
ll droot[N];

int lca(int u, int v){
    if(d[u] != d[v]){
        if(d[u] < d[v])
            swap(u, v);

        int diff = d[u] - d[v];
        for(int i = LOGN - 1; i >= 0; --i){
            if(diff >> i & 1){
                u = par[up[i][u]];
            }
        }
    }

    if(u == v)
        return u;

    for(int i = LOGN - 1; i >= 0; --i){
        if(par[up[i][u]] != par[up[i][v]]){
            u = par[up[i][u]];
            v = par[up[i][v]];
        }
    }

    return par[u];
}

void init_up(){
    for(int i = 1; i <= n; ++i){
        up[0][i] = i;
        min_up[0][i] = mdist[i] - droot[i];
    }

    for(int j = 1; j < LOGN; ++j){
        for(int i = 1; i <= n; ++i){
            up[j][i] = up[j - 1][par[up[j - 1][i]]];
            min_up[j][i] = min(min_up[j  - 1][i], min_up[j - 1][par[up[j - 1][i]]]);
        }
    }
}

void dfs(int u, int p){
    par[u] = p;

    mdist[u] = shop[u] ? 0 : INF;
    for(auto [to, w]: adj[u]){
        if(to == p)
            continue;

        d[to] = d[u] + 1;
        droot[to] = droot[u] + w;
        dfs(to, u);
        check_min(mdist[u], mdist[to] + w);
    }
}

array<int, 3> edges[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> s >> q >> e;
    for(int i = 0; i < n - 1; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});

        edges[i + 1] = {u, v, w};
    }

    for(int i = 0; i < s; ++i){
        int c;
        cin >> c;
        shop[c] = true;
    }

    dfs(e, e);
    init_up();

    for(int i = 1; i <= n - 1; ++i){
        if(d[edges[i][0]] < d[edges[i][1]])
            swap(edges[i][0], edges[i][1]);
    }

    for(int i = 0; i < q; ++i){
        int idx, r;
        cin >> idx >> r;

        if(lca(edges[idx][0], r) != edges[idx][0]){
            cout << "escaped\n";
            continue; 
        }

        ll ans = INF;
        int target_d = d[edges[idx][0]];
        int curr_d = d[r];
        
        int num_nodes = curr_d - target_d + 1;
        int cd = r;
        for(int i = LOGN - 1; i >= 0; --i)
            if(num_nodes >> i & 1){
                check_min(ans, droot[r] + min_up[i][cd]);
                cd = par[up[i][cd]];
            }

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

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