oj.uz

Submission #916705

# Submission time Handle Problem Language Result Execution time Memory
916705 2024-01-26T10:19:25 Z a_l_i_r_e_z_a Valley (BOI19_valley) C++17
100 / 100
 167 ms 48024 KB 
// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 1e5 + 5, lg = 20;
const int inf = 1e18 + 7;
int n, s, q, r, timer, h[maxn], val[maxn], dp[maxn][lg], par[maxn][lg];
int ras[maxn], in[maxn], out[maxn];
vector<pair<int, pii>> adj[maxn];
bool mark[maxn];

void dfs(int v, int p){
    in[v] = timer++;
    par[v][0] = p;
    val[v] = inf;
    if(mark[v]) val[v] = h[v];
    for(auto [u, e]: adj[v]){
        if(u != p){
            h[u] = h[v] + e.F;
            ras[e.S] = u;
            dfs(u, v);
            smin(val[v], val[u]);
        }
    }
    dp[v][0] = val[v] - 2 * h[v];
    out[v] = timer;
}

bool is_par(int u, int v){
    return in[u] <= in[v] && out[u] >= out[v];
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> s >> q >> r;
    for(int i = 1; i < n; i++){
        int u, v, w; cin >> u >> v >> w;
        adj[u].pb(mp(v, mp(w, i)));
        adj[v].pb(mp(u, mp(w, i)));
    }
    for(int i = 0; i < s; i++){
        int u; cin >> u; 
        mark[u] = 1;
    }
    dfs(r, r);
    for(int i = 0; i < lg; i++) dp[0][i] = inf;
    for(int b = 1; b < lg; b++){
        for(int i = 1; i <= n; i++){
            par[i][b] = par[par[i][b - 1]][b - 1];
            dp[i][b] = dp[i][b - 1];
            smin(dp[i][b], dp[par[i][b - 1]][b - 1]); 
        }
    }
    while(q--){
        int ind, v; cin >> ind >> v;
        int u = ras[ind];
        if(!is_par(u, v)) cout << "escaped\n";
        else{
            int x = v;
            int ans = dp[u][0];
            for(int b = lg - 1; b >= 0; b--){
                if(!is_par(par[v][b], u)){
                    smin(ans, dp[v][b]);
                    v = par[v][b];
                }
            }
            smin(ans, dp[v][0]);
            ans += h[x];
            if(ans <= 1e15) cout << ans << '\n';
            else cout << "oo\n";
        }
    }

    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 3 ms 11096 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct
4 Correct 4 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 2 ms 10860 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 3 ms 10844 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 125 ms 43808 KB Output is correct
2 Correct 122 ms 43512 KB Output is correct
3 Correct 134 ms 43700 KB Output is correct
4 Correct 165 ms 45416 KB Output is correct
5 Correct 133 ms 45596 KB Output is correct
6 Correct 164 ms 47248 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 3 ms 11096 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct
4 Correct 4 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 2 ms 10860 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 3 ms 10844 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 125 ms 43808 KB Output is correct
16 Correct 122 ms 43512 KB Output is correct
17 Correct 134 ms 43700 KB Output is correct
18 Correct 165 ms 45416 KB Output is correct
19 Correct 133 ms 45596 KB Output is correct
20 Correct 164 ms 47248 KB Output is correct
21 Correct 107 ms 43856 KB Output is correct
22 Correct 129 ms 43748 KB Output is correct
23 Correct 135 ms 43860 KB Output is correct
24 Correct 157 ms 45532 KB Output is correct
25 Correct 137 ms 47872 KB Output is correct
26 Correct 126 ms 43932 KB Output is correct
27 Correct 120 ms 43764 KB Output is correct
28 Correct 142 ms 43948 KB Output is correct
29 Correct 167 ms 45168 KB Output is correct
30 Correct 141 ms 46380 KB Output is correct
31 Correct 118 ms 43884 KB Output is correct
32 Correct 117 ms 43756 KB Output is correct
33 Correct 123 ms 44112 KB Output is correct
34 Correct 144 ms 45652 KB Output is correct
35 Correct 149 ms 48024 KB Output is correct
36 Correct 120 ms 45824 KB Output is correct