Submission #838771

#	Time	Username	Problem	Language	Result	Execution time	Memory
838771		arbuzick	Cyberland (APIO23_cyberland)	C++17	100 / 100	1297 ms	119884 KiB

cyberland

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

constexpr long double inf = 1e16 + 100;

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    vector<vector<pair<int, int>>> g(n);
    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]);
    }
    vector<int> used(n);
    used[0] = 1;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        if (v == h) {
            continue;
        }
        for (auto [u, w] : g[v]) {
            if (!used[u]) {
                used[u] = 1;
                q.push(u);
            }
        }
    }
    if (!used[h]) {
        return -1;
    }
    k = min(k, 67);
    vector<vector<long double>> dist(k + 1, vector<long double>(n, inf));
    priority_queue<pair<long double, int>> s_nw, s_nxt;
    dist[0][0] = 0;
    s_nxt.push({-dist[0][0], 0});
    for (int i = 0; i < n; ++i) {
        if (used[i] && arr[i] == 0) {
            dist[0][i] = 0;
            s_nxt.push({-dist[0][i], i});
        }
    }
    used.assign(n, -1);
    for (int i = 0; i <= k; ++i) {
        s_nw.swap(s_nxt);
        while (!s_nw.empty()) {
            int v = s_nw.top().second;
            s_nw.pop();
            if (used[v] == i) {
                continue;
            }
            used[v] = i;
            if (v == h) {
                continue;
            }
            if (dist[i][v] >= inf - 10) {
                continue;
            }
            for (auto [u, w] : g[v]) {
                if (dist[i][u] > dist[i][v] + w) {
                    dist[i][u] = dist[i][v] + w;
                    s_nw.push({-dist[i][u], u});
                }
                if (arr[v] == 2 && i + 1 <= k && dist[i + 1][u] > dist[i][v] / 2.0 + w) {
                    dist[i + 1][u] = dist[i][v] / 2.0 + w;
                    s_nxt.push({-dist[i + 1][u], u});
                }
            }
        }
    }
    long double ans = inf;
    for (int i = 0; i <= k; ++i) {
        ans = min(ans, dist[i][h]);
    }
    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