oj.uz

Submission #942327

# Submission time Handle Problem Language Result Execution time Memory
942327 2024-03-10T13:00:09 Z phoenix0423 Valley (BOI19_valley) C++17
100 / 100
 204 ms 50032 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int INF = 1e18;
int n, s, q, e;
vector<pll> adj[maxn];
int succ[maxn][18], dep[maxn], ans[maxn], val[maxn][18], st[maxn];
int d[maxn];
pll edge[maxn];
void dfs(int pos, int prev){
    succ[pos][0] = prev;
    ans[pos] = (st[pos] ? 0 : INF);
    for(int i = 1; i < 18; i++) succ[pos][i] = succ[succ[pos][i - 1]][i - 1];
    for(auto [x, w] : adj[pos]){
        if(x == prev) continue;
        dep[x] = dep[pos] + 1;
        d[x] = d[pos] + w;
        dfs(x, pos);
        ans[pos] = min(ans[pos], ans[x] + w);
    }
}

void dfs2(int pos, int prev){
    val[pos][0] = ans[succ[pos][0]] - d[succ[pos][0]];
    for(int i = 1; i < 18; i++) val[pos][i] = min(val[pos][i - 1], val[succ[pos][i - 1]][i - 1]);
    for(auto [x, w] : adj[pos]){
        if(x == prev) continue;
        dfs2(x, pos);
    }
}
int lift(int b, int steps){
    for(int i = 17; i >= 0; i--){
        if(steps & (1 << i)) b = succ[b][i];
    }
    return b;
}

signed main(void){
    fastio;
    cin>>n>>s>>q>>e;
    e--;
    for(int i = 0; i < n - 1; i++){
        int a, b, w;
        cin>>a>>b>>w;
        a--, b--;
        edge[i].f = a, edge[i].s = b;
        adj[a].eb(b, w);
        adj[b].eb(a, w);
    }
    for(int i = 0; i < s; i++){
        int c;
        cin>>c;
        st[c - 1] = 1;
    }
    dfs(e, e);
    dfs2(e, e);
    for(int i = 0; i < q; i++){
        int id, r;
        cin>>id>>r;
        id--, r--;
        auto [a, b] = edge[id];
        if(dep[r] < dep[a] || dep[r] < dep[b] || lift(r, dep[r] - dep[a]) != a || lift(r, dep[r] - dep[b]) != b){
            cout<<"escaped\n";
            continue;
        }
        if(dep[a] > dep[b]) swap(a, b);
        int mn = ans[r];
        int dif = dep[r] - dep[b], pos = r;
        for(int i = 17; i >= 0; i--){
            if(dif & (1 << i)) mn = min(mn, val[pos][i] + d[r]), pos = succ[pos][i];
        }
        if(mn >= INF) cout<<"oo\n";
        else cout<<mn<<"\n";
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10840 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct
4 Correct 4 ms 10840 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10840 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct
4 Correct 4 ms 10840 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 3 ms 10932 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10984 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10880 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 45140 KB Output is correct
2 Correct 162 ms 45132 KB Output is correct
3 Correct 147 ms 45220 KB Output is correct
4 Correct 164 ms 47188 KB Output is correct
5 Correct 148 ms 47268 KB Output is correct
6 Correct 162 ms 49364 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10840 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct
4 Correct 4 ms 10840 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 3 ms 10932 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 10984 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10880 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 132 ms 45140 KB Output is correct
16 Correct 162 ms 45132 KB Output is correct
17 Correct 147 ms 45220 KB Output is correct
18 Correct 164 ms 47188 KB Output is correct
19 Correct 148 ms 47268 KB Output is correct
20 Correct 162 ms 49364 KB Output is correct
21 Correct 116 ms 44780 KB Output is correct
22 Correct 134 ms 44612 KB Output is correct
23 Correct 129 ms 44620 KB Output is correct
24 Correct 204 ms 46948 KB Output is correct
25 Correct 167 ms 50032 KB Output is correct
26 Correct 140 ms 44628 KB Output is correct
27 Correct 120 ms 44608 KB Output is correct
28 Correct 162 ms 44884 KB Output is correct
29 Correct 144 ms 46160 KB Output is correct
30 Correct 166 ms 47804 KB Output is correct
31 Correct 112 ms 44624 KB Output is correct
32 Correct 134 ms 44532 KB Output is correct
33 Correct 129 ms 44956 KB Output is correct
34 Correct 192 ms 46988 KB Output is correct
35 Correct 149 ms 49744 KB Output is correct
36 Correct 140 ms 46676 KB Output is correct