Submission #1230328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230328		SpyrosAliv	Cyberland (APIO23_cyberland)	C++20	97 / 100	3099 ms	166332 KiB

cyberland

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

const double INF = 1e17;
int n, m, k, targ;
vector<vector<pair<int, int>>> g;
vector<vector<double>> dp;

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) {
    n = N;
    m = M;
    k = K;
    targ = H;
    g.clear();
    g.resize(n);
    for (int i = 0; i < m; i++) {
        g[x[i]].push_back({y[i], c[i]});
        g[y[i]].push_back({x[i], c[i]});
    }
    if (k >= 100) {
        k = 100;
    }
    dp.assign(n, vector<double>(k+1, INF));
    priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> pq;
    pq.push({0, 0, 0});
    for (int j = 0; j <= k; j++) dp[0][j] = 0;
    while (!pq.empty()) {
        double dis = get<0>(pq.top());
        int node = get<1>(pq.top());
        int used = get<2>(pq.top());
        pq.pop();
        if (dp[node][used] < dis || node == targ) continue;
        if (arr[node] == 0) {
            for (int i = 0; i <= k; i++) dp[node][i] = 0;
            dis = 0;
            used = 0;
        }
        for (auto [next, w]: g[node]) {
            if (dp[node][used] + w < dp[next][used]) {
                dp[next][used] = dp[node][used] + w;
                pq.push({dp[next][used], next, used});
            }
        }
        if (arr[node] != 2 || used == k) continue;
        double nextW = dis / (double)2;
        for (auto [next, w]: g[node]) {
            if (nextW + w < dp[next][used + 1]) {
                dp[next][used + 1] = nextW + w;
                pq.push({dp[next][used + 1], next, used + 1});
            }
        }
    }
    double ans = INF;
    for (int i = 0; i <= k; i++) ans = min(ans, dp[targ][i]);
    if (ans == INF) ans = -1;
    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