Submission #749134

#	Time	Username	Problem	Language	Result	Execution time	Memory
749134		Alan	Cyberland (APIO23_cyberland)	C++17	97 / 100	3066 ms	178180 KiB

cyberland

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

struct edge {
    int v;
    ld w;
    int k;
    bool operator< (edge b) const {
        if (k != b.k) return k > b.k;
        return w > b.w;
    }
};
vector<edge> g[100005];
bool vis[100005];
ld di[100005][101];
const ld inf = 1e18;
int h;

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

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) {
    h = H;
    K = min(K, 100);
    for (int i = 0; i < N; i++) {
        g[i].clear();
        vis[i] = false;
        for (int j = 0; j <= K; j++) di[i][j] = inf;
    }
    for (int i = 0; i < M; i++) {
        g[x[i]].push_back({y[i], ld(c[i]), 0});
        g[y[i]].push_back({x[i], ld(c[i]), 0});
    }
    dfs(0);
    if (!vis[H]) return -1;
    priority_queue<edge, vector<edge>> pq;
    for (int i = 1; i < N; i++) if (arr[i] == 0 && vis[i]) {
        pq.push({i, 0, 0});
        di[i][0] = 0;
    }
    pq.push({0, 0, 0});
    di[0][0] = 0;
    while (!pq.empty()) {
        auto [u, w, k] = pq.top();
        pq.pop();
        if (u == H) continue;
        if (di[u][k] != w) continue;
        for (auto& [v, vw, vk] : g[u]) if (arr[v] != 0) {
            if (arr[v] == 2 && k+1 <= K && di[v][k+1] > (w+vw)/2) {
                di[v][k+1] = (w+vw)/2;
                pq.push({v, (w+vw)/2, k+1});
            }
            if (di[v][k] > w+vw) {
                di[v][k] = w+vw;
                pq.push({v, w+vw, k});
            }
        }
    }
    ld ans = inf;
    for (int i = 0; i <= K; i++) ans = min(ans, di[H][i]);
    return ans == inf ? -1 : 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: 0 / 3