oj.uz

Submission #911089

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

const int LOG = 18, maxn = 1e5 + 5;
 
int n, s, q, e, timer = 0;
vector<vector<pii> > graph;
int store[maxn+1], in[maxn+1], out[maxn+1], depth[maxn+1], up[maxn+1][LOG];
ll dp[maxn+1], dist[maxn+1], mn[maxn+1][LOG];
 
void dfs(int u, int p) {
    in[u] = timer++;
    dp[u] = (store[u] ? dist[u] : 1e17);
 
    for(auto &[v, w] : graph[u]) {
        if(v == p) continue;
        dist[v] = dist[u] + w;
        dfs(v, u);
        dp[u] = min(dp[u], dp[v]);
    }
 
    out[u] = timer;
}

void dfs2(int u, int p) {
    for(int i=1; i<LOG; i++) {
        up[u][i] = up[ up[u][i-1] ][i-1];
        mn[u][i] = min(mn[u][i-1], mn[ up[u][i-1] ][i-1]);
    }

    for(auto &[v, _] : graph[u]) {
        if(v == p) continue;
        up[v][0] = u;
        mn[v][0] = dp[u];
        dfs2(v, u);
    }
}
 
bool anc(int u, int v) { return (in[u] <= in[v] && out[u] >= out[v]); }
 
int32_t main() {
    cin >> n >> s >> q >> e;
    vector<pii> edges;
    graph.resize(n+1);
 
    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] -= 2 * dist[u];
    dfs2(e, 0);
 
    while(q--) {
        int I, R;
        cin >> I >> R;
        pii edge = edges[I-1];
 
        if(in[edge.first] < in[edge.second]) swap(edge.first, edge.second);
        if(anc(edge.first, R) == anc(edge.first, e)) {
            cout << "escaped\n";
            continue;
        }

        ll ans = dp[R] + dist[R];
        int u = R;
        
        for(int j=LOG-1; j>=0; j--) {
            if(up[u][j] == 0 || !anc(edge.first, up[u][j])) continue;
            if(!ans) break;
            ans = min(ans, dist[R] + mn[u][j]);
            u = up[u][j];
        }

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

    return 0;
}

Compilation message

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2396 KB Output is correct
2 Correct 15 ms 2396 KB Output is correct
3 Correct 15 ms 2392 KB Output is correct
4 Correct 15 ms 2396 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2396 KB Output is correct
2 Correct 15 ms 2396 KB Output is correct
3 Correct 15 ms 2392 KB Output is correct
4 Correct 15 ms 2396 KB Output is correct
5 Correct 3 ms 2648 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 4 ms 2648 KB Output is correct
9 Correct 4 ms 2652 KB Output is correct
10 Correct 3 ms 2652 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 4 ms 2652 KB Output is correct
13 Correct 3 ms 2652 KB Output is correct
14 Correct 3 ms 2648 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 31892 KB Output is correct
2 Correct 352 ms 31616 KB Output is correct
3 Correct 350 ms 31636 KB Output is correct
4 Correct 350 ms 33348 KB Output is correct
5 Correct 352 ms 33480 KB Output is correct
6 Correct 352 ms 35464 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2396 KB Output is correct
2 Correct 15 ms 2396 KB Output is correct
3 Correct 15 ms 2392 KB Output is correct
4 Correct 15 ms 2396 KB Output is correct
5 Correct 3 ms 2648 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 4 ms 2648 KB Output is correct
9 Correct 4 ms 2652 KB Output is correct
10 Correct 3 ms 2652 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 4 ms 2652 KB Output is correct
13 Correct 3 ms 2652 KB Output is correct
14 Correct 3 ms 2648 KB Output is correct
15 Correct 374 ms 31892 KB Output is correct
16 Correct 352 ms 31616 KB Output is correct
17 Correct 350 ms 31636 KB Output is correct
18 Correct 350 ms 33348 KB Output is correct
19 Correct 352 ms 33480 KB Output is correct
20 Correct 352 ms 35464 KB Output is correct
21 Correct 323 ms 31556 KB Output is correct
22 Correct 317 ms 31596 KB Output is correct
23 Correct 308 ms 31172 KB Output is correct
24 Correct 334 ms 33416 KB Output is correct
25 Correct 325 ms 36036 KB Output is correct
26 Correct 298 ms 32140 KB Output is correct
27 Correct 299 ms 31428 KB Output is correct
28 Correct 308 ms 31432 KB Output is correct
29 Correct 375 ms 32788 KB Output is correct
30 Correct 339 ms 34132 KB Output is correct
31 Correct 294 ms 31944 KB Output is correct
32 Correct 309 ms 31712 KB Output is correct
33 Correct 330 ms 31816 KB Output is correct
34 Correct 346 ms 33476 KB Output is correct
35 Correct 351 ms 36168 KB Output is correct
36 Correct 334 ms 34108 KB Output is correct