oj.uz

Submission #636286

# Submission time Handle Problem Language Result Execution time Memory
636286 2022-08-28T19:17:24 Z erto Valley (BOI19_valley) C++17
59 / 100
 233 ms 50820 KB 
#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);

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9556 KB Output is correct
2 Correct 7 ms 9424 KB Output is correct
3 Correct 7 ms 9428 KB Output is correct
4 Correct 7 ms 9432 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9556 KB Output is correct
2 Correct 7 ms 9424 KB Output is correct
3 Correct 7 ms 9428 KB Output is correct
4 Correct 7 ms 9432 KB Output is correct
5 Correct 6 ms 9416 KB Output is correct
6 Correct 6 ms 9432 KB Output is correct
7 Correct 5 ms 9556 KB Output is correct
8 Correct 6 ms 9428 KB Output is correct
9 Correct 6 ms 9428 KB Output is correct
10 Correct 6 ms 9448 KB Output is correct
11 Correct 8 ms 9480 KB Output is correct
12 Correct 7 ms 9480 KB Output is correct
13 Correct 6 ms 9552 KB Output is correct
14 Correct 6 ms 9560 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 43652 KB Output is correct
2 Correct 233 ms 43548 KB Output is correct
3 Correct 193 ms 43524 KB Output is correct
4 Correct 219 ms 46944 KB Output is correct
5 Correct 187 ms 45912 KB Output is correct
6 Correct 195 ms 50820 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9556 KB Output is correct
2 Correct 7 ms 9424 KB Output is correct
3 Correct 7 ms 9428 KB Output is correct
4 Correct 7 ms 9432 KB Output is correct
5 Correct 6 ms 9416 KB Output is correct
6 Correct 6 ms 9432 KB Output is correct
7 Correct 5 ms 9556 KB Output is correct
8 Correct 6 ms 9428 KB Output is correct
9 Correct 6 ms 9428 KB Output is correct
10 Correct 6 ms 9448 KB Output is correct
11 Correct 8 ms 9480 KB Output is correct
12 Correct 7 ms 9480 KB Output is correct
13 Correct 6 ms 9552 KB Output is correct
14 Correct 6 ms 9560 KB Output is correct
15 Correct 174 ms 43652 KB Output is correct
16 Correct 233 ms 43548 KB Output is correct
17 Correct 193 ms 43524 KB Output is correct
18 Correct 219 ms 46944 KB Output is correct
19 Correct 187 ms 45912 KB Output is correct
20 Correct 195 ms 50820 KB Output is correct
21 Correct 181 ms 43124 KB Output is correct
22 Incorrect 182 ms 42956 KB Output isn't correct
23 Halted 0 ms 0 KB -