oj.uz

Submission #784577

# Submission time Handle Problem Language Result Execution time Memory
784577 2023-07-16T10:06:18 Z faruk Valley (BOI19_valley) C++17
100 / 100
 249 ms 66996 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const int K = 20;

struct info {
    ll length, min_cost, top_node;
    info() {length=0,min_cost=0;}
    info(ll a, ll b, ll c) {length = a, min_cost = b, top_node = c;}
};

info merge(info lower, info higher) {
    return info(lower.length + higher.length, min(lower.min_cost, higher.min_cost + lower.length), higher.top_node);
}

vector<pair<pii, ll> > edges;
vector<vector<pii> > graph;
vector<vector<info> > lift;
vector<int> in_time;
vector<int> out_time;
vector<bool> is_shop;

int tim = 0;
ll dfs(int curr, ll par, ll edge_cst) {
    ll min_cost = 1e18;
    if (is_shop[curr])
        min_cost = 0;
    in_time[curr] = tim;
    for (auto &[a, w] : graph[curr]) {
        if (a == par)
            continue;
        tim++;
        min_cost = min(min_cost, dfs(a, curr, w) + w);
    }
    lift[0][curr] = info(edge_cst, min_cost, par);
    out_time[curr] = ++tim;
    return min_cost;
}

void dfs2(int curr, ll par) {
    for (int i = 1; i < K; i++)
        lift[i][curr] = merge(lift[i - 1][curr], lift[i-1][lift[i-1][curr].top_node]);
    for (auto &[a, w] : graph[curr])
        if (a != par)
            dfs2(a, curr);
}

bool is_ancestor(int a, int b) {
    return in_time[a] <= in_time[b] and out_time[a] >= out_time[b];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, s, q, e;
    cin >> n >> s >> q >> e;
    graph = vector<vector<pii> > (n+1);
    in_time.resize(n+1);
    in_time[0] = -1e9;
    out_time.resize(n+1);
    out_time[0] = 1e9;
    edges.resize(n+1);
    is_shop.resize(n+1);
    lift.resize(K, vector<info>(n+1));

    for (int i = 0; i < n - 1; i++) {
        cin >> edges[i].first.first >> edges[i].first.second >> edges[i].second;
        graph[edges[i].first.first].push_back({edges[i].first.second, edges[i].second});
        graph[edges[i].first.second].push_back({edges[i].first.first, edges[i].second});
    }

    for (int i = 0; i < s; i++) {
        int guy;
        cin >> guy;
        is_shop[guy] = true;
    }
    dfs(e, 0, 0);
    dfs2(e, 0);

    while (q--) {
        int block, r;
        cin >> block >> r;
        block--;

        pii block_edge = edges[block].first;
        if (in_time[block_edge.first] < in_time[block_edge.second])
            swap(block_edge.first, block_edge.second);
        int block_node = block_edge.first;
    
        // checking if you can leave
        if (!is_ancestor(block_node, r)) {
            cout << "escaped\n";
            continue;
        }
        block_node = lift[0][block_edge.second].top_node;
        // now_bin_lifting
        info ans = lift[0][r];
        for (int i = K - 1; i >= 0; i--) {
            info top = lift[i][ans.top_node];
            if (is_ancestor(top.top_node, block_node))
                continue;
            ans = merge(ans, top);
        }

        if (ans.min_cost >= 1e18)
            cout << "oo\n";
        else
            cout << ans.min_cost << "\n";
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 468 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 59484 KB Output is correct
2 Correct 191 ms 62240 KB Output is correct
3 Correct 200 ms 62468 KB Output is correct
4 Correct 224 ms 64308 KB Output is correct
5 Correct 190 ms 64472 KB Output is correct
6 Correct 249 ms 66596 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 168 ms 59484 KB Output is correct
16 Correct 191 ms 62240 KB Output is correct
17 Correct 200 ms 62468 KB Output is correct
18 Correct 224 ms 64308 KB Output is correct
19 Correct 190 ms 64472 KB Output is correct
20 Correct 249 ms 66596 KB Output is correct
21 Correct 165 ms 61876 KB Output is correct
22 Correct 177 ms 61732 KB Output is correct
23 Correct 206 ms 61984 KB Output is correct
24 Correct 238 ms 63956 KB Output is correct
25 Correct 218 ms 66996 KB Output is correct
26 Correct 174 ms 61848 KB Output is correct
27 Correct 192 ms 61652 KB Output is correct
28 Correct 196 ms 61948 KB Output is correct
29 Correct 244 ms 63396 KB Output is correct
30 Correct 241 ms 64964 KB Output is correct
31 Correct 164 ms 61868 KB Output is correct
32 Correct 179 ms 61732 KB Output is correct
33 Correct 191 ms 62084 KB Output is correct
34 Correct 236 ms 63892 KB Output is correct
35 Correct 223 ms 66852 KB Output is correct
36 Correct 208 ms 63908 KB Output is correct