oj.uz

Submission #529991

# Submission time Handle Problem Language Result Execution time Memory
529991 2022-02-24T09:21:58 Z KoD Cities (BOI16_cities) C++17
100 / 100
 1625 ms 48604 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::tuple;
using std::pair;

using ll = long long;

constexpr ll inf = std::numeric_limits<ll>::max() / 2;

template <class T> using Heap = std::priority_queue<T, vector<T>, std::greater<>>;

template <class T> bool setmin(T& x, const T& y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, K, M;
    std::cin >> N >> K >> M;
    vector<int> V(K);
    for (auto& x : V) {
        std::cin >> x;
        x -= 1;
    }

    vector<vector<pair<int, int>>> graph(N);
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        std::cin >> a >> b >> c;
        a -= 1, b -= 1;
        graph[a].emplace_back(b, c);
        graph[b].emplace_back(a, c);
    }

    vector merge(N, vector(1 << K, inf));
    for (int i = 0; i < K; ++i) {
        merge[V[i]][1 << i] = 0;
    }
    for (int set = 1; set < (1 << K); ++set) {
        for (int sub = set; (sub -= 1) &= set;) {
            for (int i = 0; i < N; ++i) {
                setmin(merge[i][set], merge[i][sub] + merge[i][set & ~sub]);
            }
        }
        if (__builtin_popcount(set) >= 3) {
            continue;
        }
        Heap<pair<ll, int>> heap;
        const auto push = [&](const int u, const ll d) {
            if (setmin(merge[u][set], d)) {
                heap.emplace(d, u);
            }
        };
        for (int i = 0; i < N; ++i) {
            if (merge[i][set] != inf) {
                heap.emplace(merge[i][set], i);
            }
        }
        while (!heap.empty()) {
            const auto [d, u] = heap.top();
            heap.pop();
            if (d > merge[u][set]) {
                continue;
            }
            for (const auto& [v, c] : graph[u]) {
                push(v, d + c);
            }
        }
    }

    ll ans = inf;
    for (int i = 0; i < N; ++i) {
        setmin(ans, merge[i][(1 << K) - 1]);
    }
    std::cout << ans << '\n';

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 29616 KB Output is correct
2 Correct 566 ms 29592 KB Output is correct
3 Correct 321 ms 21836 KB Output is correct
4 Correct 56 ms 8468 KB Output is correct
5 Correct 295 ms 24236 KB Output is correct
6 Correct 52 ms 8420 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 464 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 576 KB Output is correct
2 Correct 3 ms 664 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 2 ms 464 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 967 ms 36208 KB Output is correct
2 Correct 969 ms 35948 KB Output is correct
3 Correct 643 ms 27976 KB Output is correct
4 Correct 495 ms 23160 KB Output is correct
5 Correct 126 ms 11588 KB Output is correct
6 Correct 59 ms 10056 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1625 ms 48604 KB Output is correct
2 Correct 1608 ms 48492 KB Output is correct
3 Correct 1625 ms 48444 KB Output is correct
4 Correct 1061 ms 40588 KB Output is correct
5 Correct 771 ms 29308 KB Output is correct
6 Correct 162 ms 12968 KB Output is correct
7 Correct 65 ms 10044 KB Output is correct