oj.uz

Submission #911064

# Submission time Handle Problem Language Result Execution time Memory
911064 2024-01-18T12:14:49 Z VMaksimoski008 Valley (BOI19_valley) C++14
59 / 100
 1680 ms 47160 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int LOG = 20;
 
int n, s, q, e, timer = 0;
vector<vector<pii> > graph;
vector<int> store, in, out, depth, par;
vector<vector<int> > up;
vector<vector<ll> > dp;
vector<ll> dist;
 
void dfs(int u, int p) {
    in[u] = timer++;

    if(store[u]) dp[u][0] = dist[u];
    else dp[u][0] = 1e17;
 
    for(auto &[v, w] : graph[u]) {
        if(v == p) continue;
        dist[v] = dist[u] + w;
        par[v] = u;
        dfs(v, u);
        dp[u][0] = min(dp[u][0], dp[v][0]);
    }
 
    out[u] = timer;
}
 
bool anc(int u, int v) { return (in[u] <= in[v] && out[u] >= out[v]); }
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> s >> q >> e;
    graph.resize(n+1);
    par.resize(n+1);
    in.resize(n+1);
    out.resize(n+1);
    store.resize(n+1);
    dist.resize(n+1);
    depth.resize(n+1);
    up.resize(n+1, vector<int>(LOG));
    dp.resize(n+1, vector<ll>(LOG, 1e18));
    vector<pii> edges;
 
    for(int i=0; i<n-1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edges.push_back({ a, b });
        graph[a].push_back({ b, w });
        graph[b].push_back({ a, w });
    }
 
    for(int i=0; i<s; i++) {
        int x;
        cin >> x;
        store[x] = 1;
    }
 
    dfs(e, 0);
    for(int u=1; u<=n; u++) dp[u][0] -= 2 * dist[u];

    for(pii &e : edges)
        if(in[e.first] < in[e.second]) swap(e.first, e.second);
 
    while(q--) {
        int I, R;
        cin >> I >> R;
        pii edge = edges[I-1];
 
        if(anc(edge.first, R) == anc(edge.first, e)) {
            cout << "escaped\n";
            continue;
        }

        ll ans = 1e17;
        int u = R;
        while(anc(edge.first, u) && u > 0 && ans > 0) {
            ans = min(ans, dist[R] + dp[u][0]);
            u = par[u];
        }

        if(ans >= 1e13) cout << "oo\n";
        else cout << ans << '\n';
    }
 
    
    return 0;
}

Compilation message

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:21:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for(auto &[v, w] : graph[u]) {
      |               ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 644 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 644 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 860 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 42184 KB Output is correct
2 Correct 123 ms 41668 KB Output is correct
3 Correct 125 ms 41668 KB Output is correct
4 Correct 113 ms 43460 KB Output is correct
5 Correct 123 ms 43656 KB Output is correct
6 Correct 118 ms 46244 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 644 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 114 ms 42184 KB Output is correct
16 Correct 123 ms 41668 KB Output is correct
17 Correct 125 ms 41668 KB Output is correct
18 Correct 113 ms 43460 KB Output is correct
19 Correct 123 ms 43656 KB Output is correct
20 Correct 118 ms 46244 KB Output is correct
21 Correct 108 ms 45512 KB Output is correct
22 Correct 124 ms 45000 KB Output is correct
23 Correct 126 ms 45172 KB Output is correct
24 Incorrect 1680 ms 47160 KB Output isn't correct
25 Halted 0 ms 0 KB -