Submission #1154468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154468		burgerguy	Cyberland (APIO23_cyberland)	C++20	44 / 100	30 ms	21816 KiB

cyberland

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<bool> isReachable;

void dfs(ll v, ll H, vector<vector<pair<ll,ll>>>& adj) {
    isReachable[v] = true;

    if(v == H) return;

    for(auto u : adj[v]) {
        if(!isReachable[u.first]){
            dfs(u.first, H, adj);
        }
    }
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    vector<vector<pair<ll,ll>>> adj(N);

    isReachable.clear();
    isReachable.resize(N);

    for (int i = 0; i < M; ++i) {
        adj[x[i]].emplace_back(y[i],c[i]);
        adj[y[i]].emplace_back(x[i], c[i]);
    }

    dfs(0, H, adj);

    if(!isReachable[H]) return -1;

    K = min(K, 60);
    vector<double> pwr(K + 1, 1);
    for (int i = 1; i <= K; i++)
        pwr[i] = pwr[i - 1] / 2;
    arr[0] = 0;
    vector<vector<double>> dist(K + 1, vector<double>(N, 1e18));
    using node = tuple<double, int, int>;
    priority_queue<node, vector<node>, greater<node>> pq;
    auto enq = [&](int k, int x, double d) {
        if (dist[k][x] > d) {
            dist[k][x] = d;
            pq.push({d, k, x});
        }
    };
    enq(K, H, 0);
    while (!pq.empty()) {
        auto [d, k, v] = pq.top();
        pq.pop();
        if (dist[k][v] < d)
            continue;
        if (arr[v] == 0)
            return d;
        for (auto &[w, c] : adj[v]) {
            if (!isReachable[w])
                continue;

            enq(k, w, d + c * pwr[K - k]);
            if (arr[v] == 2 && k > 0) {
                enq(k - 1, w, d + c * pwr[K - k + 1]);
            }
        }
    }
    return -1;
}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3