Submission #1126673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126673		vladilius	Valley (BOI19_valley)	C++20	100 / 100	1164 ms	165356 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = numeric_limits<ll> :: max();

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, q, E; cin>>n>>m>>q>>E;
    vector<pii> g[n + 1];
    vector<pii> ed(n);
    for (int i = 1; i < n; i++){
        int x, y, w; cin>>x>>y>>w;
        g[x].pb({y, w});
        g[y].pb({x, w});
        ed[i] = {x, y};
    }
    vector<int> a(m + 1);
    vector<bool> gd(n + 1);
    for (int i = 1; i <= m; i++){
        cin>>a[i];
        gd[a[i]] = 1;
    }
    
    const int lg = log2(n);
    vector<vector<int>> pw(n + 1, vector<int>(lg + 1));
    vector<int> tin(n + 1), tout(n + 1);
    vector<ll> d(n + 1);
    int timer = 0;
    function<void(int, int)> fill = [&](int v, int pr){
        tin[v] = ++timer;
        pw[v][0] = pr;
        for (int i = 1; i <= lg; i++){
            pw[v][i] = pw[pw[v][i - 1]][i - 1];
        }
        for (auto [i, w]: g[v]){
            if (i == pr) continue;
            d[i] = d[v] + w;
            fill(i, v);
        }
        tout[v] = timer;
    };
    fill(1, 1);
    
    auto check = [&](int x, int y){
        return (tin[x] <= tin[y] && tout[x] >= tout[y]);
    };
    
    auto lca = [&](int x, int y){
        if (check(x, y)) return x;
        if (check(y, x)) return y;
        for (int i = lg; i >= 0; i--){
            if (!check(pw[x][i], y)){
                x = pw[x][i];
            }
        }
        return pw[x][0];
    };
    
    auto on_path = [&](int x, int y, int v){
        int l = lca(x, y);
        return check(l, v) && (check(v, y) || check(v, x));
    };
    
    auto dist = [&](int x, int y){
        return d[x] + d[y] - 2 * d[lca(x, y)];
    };
    
    vector<bool> used(n + 1);
    vector<int> sz(n + 1);
    function<void(int, int)> fill_sz = [&](int v, int pr){
        sz[v] = 1;
        for (auto [i, w]: g[v]){
            if (i == pr || used[i]) continue;
            fill_sz(i, v);
            sz[v] += sz[i];
        }
    };
    
    function<int(int, int, int&)> find = [&](int v, int pr, int& S){
        for (auto [i, w]: g[v]){
            if (i == pr || used[i]) continue;
            if (2 * sz[i] >= S){
                return find(i, v, S);
            }
        }
        return v;
    };
    
    vector<int> tn(n + 1), tt(n + 1), all;
    vector<ll> ds(n + 1);
    function<void(int, int, int&)> dfs = [&](int v, int pr, int& k){
        tn[v] = ++timer;
        all.pb(v);
        for (auto [i, w]: g[v]){
            if (i == pr || used[i]) continue;
            ds[i] = ds[v] + w;
            dfs(i, v, k);
        }
        tt[v] = timer;
    };
    
    vector<ll> pf[n + 1], sf[n + 1];
    vector<int> p(n + 1);
    map<int, pii> mp[n + 1];
    function<void(int, int)> arvid = [&](int v, int P){
        fill_sz(v, 0);
        int k = find(v, 0, sz[v]);

        p[k] = P;

        used[k] = 1;
        all.clear();
        timer = ds[k] = 0;
        dfs(k, 0, k);
        
        int m = (int) all.size();
        pf[k].assign(m + 2, inf);
        sf[k].assign(m + 2, inf);
        for (int i: all){
            mp[k][i] = {tn[i], tt[i]};
            if (!gd[i]) continue;
            pf[k][tn[i]] = sf[k][tn[i]] = ds[i];
        }
        for (int i = 1; i <= m; i++){
            pf[k][i] = min(pf[k][i - 1], pf[k][i]);
        }
        for (int i = m; i > 0; i--){
            sf[k][i] = min(sf[k][i + 1], sf[k][i]);
        }
        
        for (auto [i, w]: g[k]){
            if (used[i]) continue;
            arvid(i, k);
        }
    };
    arvid(1, 0);
    
    while (q--){
        int x, y; cin>>x>>y;
        if (!on_path(E, y, ed[x].ff) || !on_path(E, y, ed[x].ss)){
            cout<<"escaped"<<"\n";
            continue;
        }
        
        int v = y;
        ll out = inf;
        while (v > 0){
            if (!on_path(v, y, ed[x].ff) || !on_path(v, y, ed[x].ss)){
                ll D = dist(v, y);
                auto it1 = mp[v].find(ed[x].ff), it2 = mp[v].find(ed[x].ss);
                if (it1 == mp[v].end() || it2 == mp[v].end()){
                    ll f = pf[v][pf[v].size() - 2];
                    if (f != inf){
                        out = min(out, D + f);
                    }
                }
                else {
                    auto [tn1, tt1] = (*it1).ss;
                    auto [tn2, tt2] = (*it2).ss;
                    
                    if (tn1 > tn2){
                        swap(tn1, tn2);
                        swap(tt1, tt2);
                    }
                    
                    ll f1 = pf[v][tn2 - 1];
                    if (f1 != inf){
                        out = min(out, D + f1);
                    }
                    ll f2 = sf[v][tt2 + 1];
                    if (f2 != inf){
                        out = min(out, D + f2);
                    }
                }
            }
            
            v = p[v];
        }
        
        if (out == inf){
            cout<<"oo"<<"\n";
        }
        else {
            cout<<out<<"\n";
        }
    }
}

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