oj.uz

Submission #645082

# Submission time Handle Problem Language Result Execution time Memory
645082 2022-09-26T06:54:57 Z mychecksedad Valley (BOI19_valley) C++17
100 / 100
 214 ms 63312 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;



int n, s, q, E, tin[N], tout[N], timer = 0, up[N][K], dep[N];
vector<bool> c(N);
vector<array<int, 2>> g[N], edges;
ll dist[N], dp[N][K], d[N];
void pre(int v, int p){
    tin[v] = timer++;
    up[v][0] = p;
    dist[v] = 1e18;
    dep[v] = dep[p] + 1;
    for(auto k: g[v]){
        if(k[0] != p){
            d[k[0]] = d[v] + k[1];
            pre(k[0], v);
            dist[v] = min(dist[v], dist[k[0]] + k[1]);
        }
    }
    
    if(c[v]) dist[v] = 0;
    tout[v] = timer++;
}

bool is_ancestor(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

void solve(){
    cin >> n >> s >> q >> E;
    for(int i = 0; i < n - 1; ++i){
        int u, v, e; cin >> u >> v >> e;
        g[u].pb({v, e});
        g[v].pb({u, e});
        edges.pb({u, v});
    }
    for(int i = 1; i <= s; ++i){
        int x; cin >> x;
        c[x] = 1;
    }
    d[E] = dep[E] = 0;
    pre(E, E);
    for(int i = 1; i <= n; ++i) dp[i][0] = min(dist[i], dist[up[i][0]] + (d[i] - d[up[i][0]]));
    for(int j = 1; j < K; ++j){
        for(int i = 1; i <= n; ++i){
            up[i][j] = up[up[i][j - 1]][j - 1]; 
            dp[i][j] = min(dp[i][j - 1], dp[up[i][j - 1]][j - 1] + (d[i] - d[up[i][j - 1]]));
        }
    }

    for(;q--;){
        int i, v; cin >> i >> v;
        int a = edges[i - 1][0], b = edges[i - 1][1];
        if(is_ancestor(a, b)) swap(a, b);
        if(!is_ancestor(a, v)){
            cout << "escaped";
        }else{
            ll best = dist[v], cur = 0;
            for(int i = K - 1; i >= 0; --i){
                if((1<<i)&(dep[v] - dep[a])){
                    best = min(best, dp[v][i] + cur);
                    cur += d[v] - d[up[v][i]];
                    v = up[v][i];
                }
            }
            if(best == 1e18) cout << "oo";
            else cout << best;
        }
        cout << '\n';
    }      
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:92:16: warning: unused variable 'aa' [-Wunused-variable]
   92 |     int T = 1, aa;
      |                ^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 15 ms 24084 KB Output is correct
3 Correct 18 ms 24148 KB Output is correct
4 Correct 14 ms 24140 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 15 ms 24084 KB Output is correct
3 Correct 18 ms 24148 KB Output is correct
4 Correct 14 ms 24140 KB Output is correct
5 Correct 14 ms 24276 KB Output is correct
6 Correct 14 ms 24300 KB Output is correct
7 Correct 13 ms 24276 KB Output is correct
8 Correct 15 ms 24268 KB Output is correct
9 Correct 13 ms 24216 KB Output is correct
10 Correct 14 ms 24240 KB Output is correct
11 Correct 13 ms 24276 KB Output is correct
12 Correct 17 ms 24236 KB Output is correct
13 Correct 13 ms 24284 KB Output is correct
14 Correct 14 ms 24276 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 55496 KB Output is correct
2 Correct 197 ms 55220 KB Output is correct
3 Correct 163 ms 55136 KB Output is correct
4 Correct 187 ms 56856 KB Output is correct
5 Correct 162 ms 57024 KB Output is correct
6 Correct 200 ms 58844 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 15 ms 24084 KB Output is correct
3 Correct 18 ms 24148 KB Output is correct
4 Correct 14 ms 24140 KB Output is correct
5 Correct 14 ms 24276 KB Output is correct
6 Correct 14 ms 24300 KB Output is correct
7 Correct 13 ms 24276 KB Output is correct
8 Correct 15 ms 24268 KB Output is correct
9 Correct 13 ms 24216 KB Output is correct
10 Correct 14 ms 24240 KB Output is correct
11 Correct 13 ms 24276 KB Output is correct
12 Correct 17 ms 24236 KB Output is correct
13 Correct 13 ms 24284 KB Output is correct
14 Correct 14 ms 24276 KB Output is correct
15 Correct 150 ms 55496 KB Output is correct
16 Correct 197 ms 55220 KB Output is correct
17 Correct 163 ms 55136 KB Output is correct
18 Correct 187 ms 56856 KB Output is correct
19 Correct 162 ms 57024 KB Output is correct
20 Correct 200 ms 58844 KB Output is correct
21 Correct 150 ms 58808 KB Output is correct
22 Correct 181 ms 58500 KB Output is correct
23 Correct 158 ms 58452 KB Output is correct
24 Correct 171 ms 60460 KB Output is correct
25 Correct 214 ms 63312 KB Output is correct
26 Correct 134 ms 58816 KB Output is correct
27 Correct 144 ms 58552 KB Output is correct
28 Correct 178 ms 58464 KB Output is correct
29 Correct 191 ms 59876 KB Output is correct
30 Correct 191 ms 61260 KB Output is correct
31 Correct 180 ms 58936 KB Output is correct
32 Correct 157 ms 58548 KB Output is correct
33 Correct 161 ms 58804 KB Output is correct
34 Correct 192 ms 60428 KB Output is correct
35 Correct 174 ms 63108 KB Output is correct
36 Correct 169 ms 60516 KB Output is correct