oj.uz

답안 #911065

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911065 2024-01-18T12:15:37 Z VMaksimoski008 Valley (BOI19_valley) C++14
59 / 100
 3000 ms 48324 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 >= 1e15) 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 548 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 548 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 856 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 1016 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 856 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

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 41988 KB Output is correct
2 Correct 109 ms 41672 KB Output is correct
3 Correct 113 ms 41672 KB Output is correct
4 Correct 150 ms 43464 KB Output is correct
5 Correct 123 ms 43584 KB Output is correct
6 Correct 111 ms 45508 KB Output is correct

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 548 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 856 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 1016 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 120 ms 41988 KB Output is correct
16 Correct 109 ms 41672 KB Output is correct
17 Correct 113 ms 41672 KB Output is correct
18 Correct 150 ms 43464 KB Output is correct
19 Correct 123 ms 43584 KB Output is correct
20 Correct 111 ms 45508 KB Output is correct
21 Correct 90 ms 42072 KB Output is correct
22 Correct 115 ms 41928 KB Output is correct
23 Correct 108 ms 41668 KB Output is correct
24 Correct 1697 ms 43840 KB Output is correct
25 Execution timed out 3066 ms 48324 KB Time limit exceeded
26 Halted 0 ms 0 KB -