Submission #936305

#	Time	Username	Problem	Language	Result	Execution time	Memory
936305		Szil	Cyberland (APIO23_cyberland)	C++17	100 / 100	810 ms	64848 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;
using ld = double;

const int MAXN = 100'001;
const int MAXK = 67;

struct Q {
    ld d;
    int u, k;

    bool operator<(const Q &x) const {
        if (k == x.k) return d > x.d;
        return k > x.k;
    }
};

vector<pair<int, ld>> g[MAXN];
ld dist[MAXN][MAXK];
bool vis[MAXN];

void dfs(int u, int H) {
    vis[u] = true;
    if (u == H) return;
    for (auto [v, w] : g[u]) {
        if (!vis[v]) dfs(v, H);
    }
}

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) {
    K = min(K, MAXK-1);

    for (int i = 0; i < N; i++) {
        g[i].clear();
        vis[i] = false;
        for (int j = 0; j <= K; j++) {
            dist[i][j] = 1e18;
        }
    }
    for (int i = 0; i < M; i++) {
        g[x[i]].emplace_back(y[i], c[i]);
        g[y[i]].emplace_back(x[i], c[i]);
    }
    dfs(0, H);
    if (!vis[H]) {
        return -1;
    }
    priority_queue<Q> pq;
    for (int i = 0; i < N; i++) {
        if (vis[i] && (arr[i] == 0 || i == 0)) {
            pq.push({0, i, 0});
            dist[i][0] = 0;
        }
    }
    while (!pq.empty()) {
        auto [d, u, k] = pq.top(); pq.pop();
        if (u == H || d > dist[u][k]) continue;
        for (auto [v, w] : g[u]) {
            if (arr[v] == 0) continue;
            ld cost = dist[u][k] + w;
            if (dist[v][k] > cost) {
                dist[v][k] = cost;
                pq.push({cost, v, k});
            }
            cost /= 2;
            if (arr[v] == 2 && k < K && dist[v][k+1] > cost) {
                dist[v][k+1] = cost;
                pq.push({cost, v, k+1});
            }
        }
    }
    ld ans = 1e18;
    for (int i = 0; i <= K; i++) {
        ans = min(ans, dist[H][i]);
    }
    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: 3 / 3