Submission #636287

#	Time	Username	Problem	Language	Result	Execution time	Memory
636287		erto	Valley (BOI19_valley)	C++17	100 / 100	263 ms	55204 KiB

valley

#include <bits/stdc++.h>
typedef long long int ll;
#define INF (ll)(1e15 + 7)
#define INF2 998244353ll
#define N (ll)(1e5 + 5)
using namespace std;
#define int ll
#define lsb(x) (x & (-x))

int n, s, q, e, g, h, t;
int d[N], depth[N];
array<int, 3> edges[N];
vector<pair<int, int>> v[N];
bool shop[N];
int dp1[N];
int dp2[N];
int par[N][20];
int cur = 1;
int st[N], en[N], ans[N];
vector<pair<int ,int>> z[N];

struct segTree{
    int n;
    vector<int> tree, minn;
    segTree(int _n){
        n = _n + 1;
        while(n != lsb(n))n += lsb(n);
        tree.resize(2 * n, INF);
        minn.resize(2 * n, INF);
    }

    void push(int i){
        if(minn[i] == INF)return;
        minn[i * 2] = min(minn[i], minn[i * 2]);
        minn[i * 2 + 1] = min(minn[i], minn[i * 2 + 1]);
        tree[i * 2] = min(minn[i], tree[i * 2]);
        tree[i * 2 + 1] = min(minn[i], tree[i * 2 + 1]);
        minn[i] = INF;
    }

    void update(int ql, int qr, int val){if(val >= INF)return; update(1, 0, n - 1, ql, qr, val);}
    void update(int i, int lb, int rb, int ql, int qr, int val){
        if(ql > rb || qr < lb)return;
        if(ql <= lb && rb <= qr){
            minn[i] = min(minn[i], val);
            tree[i] = min(tree[i], val);
            return;
        }
        int mid = (lb + rb) / 2;
        push(i);
        update(i * 2, lb, mid ,ql, qr, val);
        update(i * 2 + 1, mid + 1, rb ,ql, qr, val);
        tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
    }

    int calc(int ql, int qr){return calc(1, 0, n - 1, ql, qr);}
    int calc(int i, int lb, int rb, int ql, int qr){
        if(ql > rb || qr < lb)return INF;
        if(ql <= lb && rb <= qr){
            return tree[i];
        }
        int mid = (lb + rb) / 2;
        push(i);
        return min(calc(i * 2, lb, mid, ql, qr), calc(i * 2 + 1, mid + 1, rb, ql, qr));
    }
};

bool isanc(int x, int y){
    return (st[y] <= st[x] && en[y] >= en[x]);
}

segTree ss(N * 2);

void dfs(int x ,int p){
    par[x][0] = p;
    st[x] = cur++;
    for(auto u : v[x]){
        if(u.first != p){
            d[u.first] = d[x] + u.second;
            depth[u.first] = depth[x] + 1;
            dfs(u.first, x);
            dp1[x] = min(dp1[x], dp1[u.first] + u.second);
        }
    }
    en[x] = cur++;
}

void dfs2(int x, int p){
    int min1 = INF, min2 = INF;

    for(auto u : v[x]){
        if(u.first != p){
            dfs2(u.first, x);
        }
    }

    for(auto u : v[x]){
        if(u.first != p){
            g = dp1[u.first] + u.second;
            if(g <= min1){
                min2 = min1;
                min1 = g;
            }
            else if(g < min2){
                min2 = g;
            }
        }
    }

    if(shop[x])min1 = min2 = 0;

    for(auto u : v[x]){
        if(u.first != p){
            g = dp1[u.first] + u.second;
            if(g == min1){
                ss.update(st[u.first], en[u.first], min2 - d[x]);
            }
            else{
                ss.update(st[u.first], en[u.first], min1 - d[x]);
            }
        }
    }

    for(auto u : z[x]){
        ans[u.second] = min(ans[u.second], d[u.first] + ss.calc(st[u.first], st[u.first]));
    }
}

void solve(){
    cin >> n >> s >> q >> e;
    for(int i=1; i<n; i++){
        cin >> g >> h >> t;
        edges[i] = {g, h, t};
        v[g].push_back({h, t});
        v[h].push_back({g, t});
    }

    for(int i=1; i<=n; i++){
        dp1[i] = INF;
        dp2[i] = INF;
    }

    for(int i=1; i<=s; i++){
        cin >> g;
        shop[g] = 1;
        dp1[g] = 0;
        dp2[g] = 0;
    }

    dfs(e, 0);


    for(int i=1; i<20; i++){
        for(int j=1; j<=n; j++){
            par[j][i] = par[par[j][i - 1]][i - 1];
        }
    }

    int u, v;
    for(int i=1; i<=q; i++){
        cin >> g >> h;
        u = edges[g][0];
        v = edges[g][1];
        ans[i] = INF;

        if(isanc(h, u) && isanc(h, v)){
            if(d[u] < d[v]){
                z[v].push_back({h, i});
            }
            else{
                z[u].push_back({h, i});
            }
            ans[i] = dp1[h];
        }
        else{
            ans[i] = -1;
        }
    }
    dfs2(e, 0);

    for(int i=1; i<=q; i++){
        if(ans[i] == - 1){
            cout << "escaped\n";
        }
        else if(ans[i] >= INF){
            cout << "oo\n";
        }
        else{
            cout << ans[i] << '\n';
        }
    }
}   
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    while (T--){
        solve();
    }
}

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