oj.uz

Submission #825715

# Submission time Handle Problem Language Result Execution time Memory
825715 2023-08-15T07:16:56 Z Shreyan_Paliwal Valley (BOI19_valley) C++17
100 / 100
 449 ms 52504 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn = 200005;
const int INF = 1LL << 60;

int n, s, q, e;

vector<pair<int,int>> adj[maxn];
pair<int,int> edges[maxn];

int dist[maxn];
int dpth[maxn];
int closest[maxn];
int shop[maxn];

int bl[maxn][20];
int bld[maxn][20];
int st[maxn], en[maxn], cur = 0;

void dfs(int nd, int par, int d) {
    st[nd] = cur++;
    dist[nd] = dist[par] + d;
    dpth[nd] = dpth[par] + 1;

    for (auto i : adj[nd])
        if (i.first != par)
            dfs(i.first, nd, i.second);

    closest[nd] = (shop[nd] ? dist[nd] : INF);
    for (auto i : adj[nd])
        if (i.first != par && closest[i.first] != INF)
            closest[nd] = min(closest[nd], closest[i.first]);
    
    en[nd] = cur++;
}

void dfs_bl(int nd, int par) {
    bl[nd][0] = par;
    bld[nd][0] = (closest[nd] == INF ? INF : closest[nd] - 2 * dist[nd]);

    for (int i = 1; i < 20; i++) bl[nd][i] = bl[bl[nd][i-1]][i-1];
    for (int i = 1; i < 20; i++) bld[nd][i] = min(bld[nd][i-1], bld[bl[nd][i-1]][i-1]);

    for (auto i : adj[nd])
        if (i.first != par)
            dfs_bl(i.first, nd);
}

signed main() {
    cin >> n >> s >> q >> e; e--;

    for (int i = 0; i < n-1; i++) {
        int a, b, c; cin >> a >> b >> c; a--, b--;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
        edges[i] = make_pair(a, b);
    }

    for (int i = 0; i < s; i++) {
        int a; cin >> a; a--;
        shop[a] = 1;
    }

    dfs(e, e, 0);
    dfs_bl(e, e);
    
    
    for (int i = 0; i < n-1; i++)
        if (dpth[edges[i].first] < dpth[edges[i].second])
            swap(edges[i].first, edges[i].second);

    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b; a--, b--;

        // can escape?
        if (!(st[edges[a].first] <= st[b] && en[b] <= en[edges[a].first])) {
            cout << "escaped" << endl;
            continue;
        }

        int cost = INF;
        int nd = b;
        for (int i = 19; i >= 0; i--)
            if (((dpth[b] - dpth[edges[a].first]) >> i) & 1)
                cost = min(cost, bld[nd][i]), 
                nd = bl[nd][i];
        cost = min(cost, bld[nd][0]);

        if (cost == INF) { cout << "oo" << endl; continue; }

        cout << cost + dist[b] << endl;
        continue;
    }

    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5132 KB Output is correct
2 Correct 15 ms 5076 KB Output is correct
3 Correct 19 ms 5164 KB Output is correct
4 Correct 16 ms 5140 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5132 KB Output is correct
2 Correct 15 ms 5076 KB Output is correct
3 Correct 19 ms 5164 KB Output is correct
4 Correct 16 ms 5140 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 4 ms 5460 KB Output is correct
11 Correct 5 ms 5496 KB Output is correct
12 Correct 5 ms 5460 KB Output is correct
13 Correct 5 ms 5508 KB Output is correct
14 Correct 4 ms 5460 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 48360 KB Output is correct
2 Correct 330 ms 48128 KB Output is correct
3 Correct 411 ms 48344 KB Output is correct
4 Correct 356 ms 50016 KB Output is correct
5 Correct 361 ms 49996 KB Output is correct
6 Correct 428 ms 51684 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5132 KB Output is correct
2 Correct 15 ms 5076 KB Output is correct
3 Correct 19 ms 5164 KB Output is correct
4 Correct 16 ms 5140 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 4 ms 5460 KB Output is correct
11 Correct 5 ms 5496 KB Output is correct
12 Correct 5 ms 5460 KB Output is correct
13 Correct 5 ms 5508 KB Output is correct
14 Correct 4 ms 5460 KB Output is correct
15 Correct 306 ms 48360 KB Output is correct
16 Correct 330 ms 48128 KB Output is correct
17 Correct 411 ms 48344 KB Output is correct
18 Correct 356 ms 50016 KB Output is correct
19 Correct 361 ms 49996 KB Output is correct
20 Correct 428 ms 51684 KB Output is correct
21 Correct 289 ms 47604 KB Output is correct
22 Correct 309 ms 47480 KB Output is correct
23 Correct 356 ms 47692 KB Output is correct
24 Correct 342 ms 49364 KB Output is correct
25 Correct 339 ms 51836 KB Output is correct
26 Correct 311 ms 47912 KB Output is correct
27 Correct 344 ms 47800 KB Output is correct
28 Correct 315 ms 47944 KB Output is correct
29 Correct 365 ms 49184 KB Output is correct
30 Correct 387 ms 50528 KB Output is correct
31 Correct 339 ms 48396 KB Output is correct
32 Correct 347 ms 48344 KB Output is correct
33 Correct 360 ms 48512 KB Output is correct
34 Correct 390 ms 50144 KB Output is correct
35 Correct 449 ms 52504 KB Output is correct
36 Correct 377 ms 50472 KB Output is correct