제출 #1228054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228054		Dzadzo	Cyberland (APIO23_cyberland)	C++20	20 / 100	1026 ms	2162688 KiB

cyberland

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

double solve(int N, int M, int K, int H,
             vector<int> x,
              vector<int> y,
              vector<int> c,
              vector<int> arr) {
    // build graph
    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]});
    }

    // dp[v][d] = min time to reach v having used d divides
    const double INF = 1e18;
    vector<vector<double>> dp(N, vector<double>(K+1, INF));
    dp[0][0] = 0.0;

    // min‑heap by (time, v, used_divs)
    using State = tuple<double,int,int>;
    priority_queue<State, vector<State>, greater<State>> pq;
    pq.emplace(0.0, 0, 0);

    while (!pq.empty()) {
        auto [t, v, d] = pq.top(); 
        pq.pop();
        if (t > dp[v][d]) continue;
        if (v == H) break;           // once we pop H with current best t, that's optimal
        for (auto [u, w] : adj[v]) {
            // 1) move without using ability
            double t1 = t + w;
            if (t1 < dp[u][d]) {
                dp[u][d] = t1;
                pq.emplace(t1, u, d);
            }
            // 2) if u has reset ability
            if (arr[u] == 0) {
                double t0 = 0.0;
                if (t0 < dp[u][d]) {
                    dp[u][d] = t0;
                    pq.emplace(t0, u, d);
                }
            }
            // 3) if u has divide‑by‑2 and we have quota
            if (arr[u] == 2 && d < K) {
                double t2 = (t + w) / 2.0;
                if (t2 < dp[u][d+1]) {
                    dp[u][d+1] = t2;
                    pq.emplace(t2, u, d+1);
                }
            }
        }
    }

    // answer is the best over all ways to arrive at H
    double ans = INF;
    for (int d = 0; d <= K; d++) 
        ans = min(ans, dp[H][d]);
    return ans == INF ? -1.0 : ans;
}

• Subtask 1: 5 / 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