Submission #974224

#	Time	Username	Problem	Language	Result	Execution time	Memory
974224		Pannda	Cyberland (APIO23_cyberland)	C++17	97 / 100	656 ms	37836 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;

double solve(int n, int m, int k, int t, vector<int> U, vector<int> V, vector<int> W, vector<int> type) {
    k = min(k, 30);
    vector<vector<array<int, 2>>> adj(n);
    for (int i = 0; i < m; i++) {
        auto [u, v, w] = array<int, 3>{U[i], V[i], W[i]};
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    constexpr double INF = 1e18;
    constexpr double EPS = 1e-9;
    auto equal = [](double x, double y) -> bool {
        return abs(x - y) < EPS;
    };

    vector<vector<double>> dist(n, vector<double>(k + 1, INF));
    dist[t][0] = 0;
    priority_queue<pair<double, pair<int, int>>, vector<pair<double, pair<int, int>>>, greater<>> pq;
    pq.push(make_pair(dist[t][0], make_pair(0, t)));
    while (!pq.empty()) {
        auto [d, cu] = pq.top();
        auto [c, u] = cu;
        pq.pop();
        if (!equal(dist[u][c], d)) continue;
        for (auto [v, ww] : adj[u]) {
            if (v == t) continue;
            double w = ww;
            w /= (1 << c);
            if (d + w + EPS < dist[v][c]) {
                dist[v][c] = d + w;
                pq.push(make_pair(dist[v][c], make_pair(c, v)));
            }
            if (type[v] == 2 && c + 1 <= k) {
                c++;
                if (d + w + EPS < dist[v][c]) {
                    dist[v][c] = d + w;
                    pq.push(make_pair(dist[v][c], make_pair(c, v)));
                }
                c--;
            }
        }
    }

    type[0] = 0;
    vector<bool> reachable(n, false);
    queue<int> que;
    reachable[0] = true;
    que.push(0);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto [v, w] : adj[u]) {
            if (v == t) continue;
            if (!reachable[v]) {
                reachable[v] = true;
                que.push(v);
            }
        }
    }

    double ans = INF;
    for (int u = 0; u < n; u++) {
        if (reachable[u] && type[u] == 0) {
            double val = *min_element(dist[u].begin(), dist[u].end());
            ans = min(ans, val);
        }
    }

    if (equal(ans, INF)) {
        return -1;
    } else {
        return ans;
    }

}

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