Submission #1158472

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

cyberland

#include "cyberland.h"
#include <vector>
#include <queue>
#include <functional>
#include <cmath>
using namespace std;

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

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 the undirected graph.
    vector<vector<pair<int,int>>> adj(N);
    for (int i = 0; i < M; i++) {
        int u = x[i], v = y[i], w = c[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    // DFS from node 0 (source) but stop if H is reached.
    // Only nodes visited here are considered "reachable" (by 0 without passing through H).
    vector<bool> reachable(N, false);
    function<void(int)> dfs = [&](int u) {
        reachable[u] = true;
        for (auto &edge : adj[u]) {
            int v = edge.first;
            if (v == H) continue; // do not traverse beyond H
            if (!reachable[v]) dfs(v);
        }
    };
    dfs(0);
    
    // Reverse Dijkstra: We start at H and only relax edges to nodes that were marked reachable.
    // Here the state is (node, used) where used is the number of divide-by-2 abilities already used.
    // When moving from a state (u, used) to neighbor v along an edge of weight w,
    // we add an extra cost of w / (2^(used)).
    // Additionally, if u has the divide-by-2 ability (arr[u]==2) and used < K,
    // we may “activate” it: in the reverse search this means the total cost becomes d/2,
    // and future edges will be divided by a larger power of 2.
    
    int K_lim = K;  // we use K as given (if needed, one could cap it at 100 as per the outline)
    vector<vector<ld>> dist(N, vector<ld>(K_lim+1, INF));
    
    struct State { 
        ld cost; 
        int node, used;
    };
    auto cmp = [&](const State &a, const State &b) { return a.cost > b.cost; };
    priority_queue<State, vector<State>, decltype(cmp)> pq(cmp);
    
    // Start from Cyberland (node H) with cost 0 and no divide ability used.
    dist[H][0] = 0;
    pq.push({0, H, 0});
    
    while (!pq.empty()) {
        State cur = pq.top();
        pq.pop();
        ld d = cur.cost;
        int u = cur.node, used = cur.used;
        if (d != dist[u][used]) continue;
        
        // If we have reached node 0 or a node whose ability clears (arr[u]==0),
        // then this state gives the minimum possible total cost.
        if (u == 0 || arr[u] == 0)
            return (double)d;
        
        // Option 1: Use divide-by-2 ability at node u if available.
        // (This “activates” the ability in reverse, which halves the current cost.)
        if (arr[u] == 2 && used < K_lim) {
            ld nd = d / 2.0;
            if (nd < dist[u][used+1]) {
                dist[u][used+1] = nd;
                pq.push({nd, u, used+1});
            }
        }
        
        // Option 2: Relax all edges from node u.
        // The cost to go from u to a neighbor v is increased by (edge weight) / (2^(used)).
        // We use powl to compute 2^(used) in long double.
        ld discount = powl(2.0L, used);
        for (auto &edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (!reachable[v]) continue; // only consider nodes reachable from 0.
            ld nd = d + ((ld)w) / discount;
            if (nd < dist[v][used]) {
                dist[v][used] = nd;
                pq.push({nd, v, used});
            }
        }
    }
    
    return -1;
}

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