Submission #985360

#	Time	Username	Problem	Language	Result	Execution time	Memory
985360		CrazyBotBoy	Cyberland (APIO23_cyberland)	C++17	15 / 100	382 ms	20572 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;

const int MAXN = 100005;

struct disj {
    int pa[MAXN];
    void init(int n) { iota(pa, pa + n + 1, 0); }
    int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }
    bool uni(int p, int q) {
        p = find(p);
        q = find(q);
        if (p == q)
            return 0;
        pa[q] = p;
        return 1;
    }
} disj;

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, 69);  // Limiting K to a reasonable value to handle large inputs
    vector<vector<pi>> gph(N);
    disj.init(N);
    for (int i = 0; i < M; i++) {
        if (x[i] != H && y[i] != H)
            disj.uni(x[i], y[i]);
        gph[x[i]].push_back({c[i], y[i]});
        gph[y[i]].push_back({c[i], x[i]});
    }

    vector<double> pwr(K + 1, 1);
    for (int i = 1; i <= K; i++)
        pwr[i] = pwr[i - 1] / 2;

    arr[0] = 0;  // Ensuring starting point has no special ability
    vector<vector<double>> dist(K + 1, vector<double>(N, 1e18));
    using node = tuple<double, int, int>;
    priority_queue<node, vector<node>, greater<node>> pq;

    auto enq = [&](int k, int x, double d) {
        if (dist[k][x] > d) {
            dist[k][x] = d;
            pq.push({d, k, x});
        }
    };

    enq(K, 0, 0);  // Start from country 0 with full divide-by-2 abilities

    while (!pq.empty()) {
        auto [d, k, v] = pq.top();
        pq.pop();
        if (dist[k][v] < d)
            continue;
        if (v == H)
            return d;  // Return the distance once Cyberland is reached
        for (auto &[cost, w] : gph[v]) {
            enq(k, w, d + cost);
            if (arr[w] == 2 && k > 0) {
                enq(k - 1, w, d + cost * pwr[K - k + 1]);
            } else if (arr[w] == 0) {
                enq(k, w, 0);  // If the country's ability sets time to 0
            }
        }
    }
    return -1;  // If Cyberland is not reachable
}

• 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