Submission #1158477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158477		farrellw	Cyberland (APIO23_cyberland)	C++20	20 / 100	946 ms	2162688 KiB

cyberland

#include "cyberland.h"

#include <vector>
#include <queue>
#include <limits>
#include <iostream>

using namespace std;

typedef long double ld;
const ld INF = 1e18;

struct State {
    ld dist;   // total time so far
    int used;  // how many times we've used "divide by 2"
    int node;
    
    // For priority_queue in ascending order of dist
    bool operator>(const State &other) const {
        return dist > other.dist;
    }
};

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)
{
    // Build adjacency list: adj[u] = list of (v, cost)
    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]});
    }

    // Optional: check if H is reachable from 0 by a simple BFS/DFS
    // so we can return -1 quickly if not.
    // -------------------------------------------------------------
    {
        vector<bool> visited(N, false);
        queue<int>q;
        q.push(0);
        visited[0] = true;
        while(!q.empty()) {
            int cur = q.front(); q.pop();
            for (auto &nx : adj[cur]) {
                int nxt = nx.first;
                if(!visited[nxt]) {
                    visited[nxt] = true;
                    q.push(nxt);
                }
            }
        }
        if(!visited[H]) {
            return -1.0; 
        }
    }
    // -------------------------------------------------------------

    // dist[node][used] = best time to reach `node` using "divide-by-2" `used` times
    vector<vector<ld>> dist(N, vector<ld>(K+1, INF));
    dist[0][0] = 0.0;

    // Min-heap for Dijkstra-like expansions
    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push(State{0.0, 0, 0}); // (distance=0, used=0, node=0)

    while(!pq.empty()) {
        auto [cdist, used, node] = pq.top();
        pq.pop();
        
        // If this is not our best known distance, skip
        if (cdist > dist[node][used]) continue;
        
        // If we've reached Cyberland H, we're done!
        if (node == H) {
            return (double)cdist;
        }
        
        // Relax edges from current node
        for (auto &edge : adj[node]) {
            int nxt = edge.first;
            ld roadCost = (ld)edge.second;
            
            // The base cost to arrive at `nxt` before applying `nxt`'s ability
            ld baseNewDist = cdist + roadCost;
            
            // 1) We can arrive without using any new "divide-by-2" ability:
            //    - If nxt has arr[nxt] == 0, we can zero out the total.
            //    - If nxt has arr[nxt] == 2, we can choose not to halve it,
            //      so the time remains baseNewDist.
            //    - If nxt has arr[nxt] == 1, also remains baseNewDist.
            ld candidateDist = baseNewDist;
            if (arr[nxt] == 0) {
                candidateDist = 0.0;
            }
            // No halving used here, so used stays the same
            if (candidateDist < dist[nxt][used]) {
                dist[nxt][used] = candidateDist;
                pq.push(State{candidateDist, used, nxt});
            }

            // 2) If nxt == 2, we also have the *option* to halve after arriving,
            //    provided we still have an available "divide-by-2" use left.
            if (arr[nxt] == 2 && used < K) {
                ld halvedDist = baseNewDist / 2.0;
                if (halvedDist < dist[nxt][used + 1]) {
                    dist[nxt][used + 1] = halvedDist;
                    pq.push(State{halvedDist, used + 1, nxt});
                }
            }
        }
    }

    // If we exhaust the queue without reaching H, it's impossible.
    return -1.0;
}

• 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