Submission #1253802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253802		anfi	Cyberland (APIO23_cyberland)	C++20	15 / 100	300 ms	21404 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const double inf = 1e30;

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    K = min(K, 70);
    vector<vector<double>> dp(N, vector<double>(K+1, inf));
    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }

    if (H == 0) {
        return 0.0;
    }

    priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> pq;
    dp[H][0] = 0.0;
    pq.push({0.0, H, 0});

    while (!pq.empty()) {
        auto [cost, u, j] = pq.top();
        pq.pop();

        if (abs(cost - dp[u][j]) > 1e-9 && cost > dp[u][j]) 
            continue;
        
        if (u == 0) 
            continue;
        
        if (arr[u] == 0) {
            if (cost < dp[0][j]) {
                dp[0][j] = cost;
                pq.push({cost, 0, j});
            }
        }

        for (auto &[v, w] : adj[u]) {
            double new_cost = cost + w;
            if (new_cost < dp[v][j]) {
                dp[v][j] = new_cost;
                pq.push({new_cost, v, j});
            }

            if (arr[u] == 2 && j < K) {
                double halved_cost = cost + (double)w / 2.0;
                if (halved_cost < dp[v][j+1]) {
                    dp[v][j+1] = halved_cost;
                    pq.push({halved_cost, v, j+1});
                }
            }
        }
    }

    double ans = inf;
    for (int j = 0; j <= K; j++) {
        if (dp[0][j] < ans) {
            ans = dp[0][j];
        }
    }

    if (ans >= inf) {
        return -1.0;
    } else {
        return ans;
    }
}

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