Submission #1232115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232115		dizzy_groovy	Cyberland (APIO23_cyberland)	C++20	15 / 100	1349 ms	26356 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;

const double INF = 1e15;

void dfs(int i, vector<bool> &used, vector<vector<pair<int, double>>> &gr) {
    if (used[i]) return;
    used[i] = true;
    for (auto &x : gr[i]) dfs(x.first, used, gr);
}

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) {
    if (k > 30) k = 30;
    vector<vector<double>> dist(k + 1, vector<double> (n, INF));
    vector<vector<pair<int, double>>> gr(n);
    for (int i = 0; i < m; i++) {
        gr[x[i]].push_back({y[i], c[i]});
        gr[y[i]].push_back({x[i], c[i]});
    }
    vector<bool> used(n);
    dfs(0, used, gr);
    if (!used[h]) return -1;
    vector<int> st(1, 0);
    for (int i = 0; i < n; i++) {
        if (used[i] && arr[i] == 0) st.push_back(i);
    }
    set<pair<double, int>> s;
    for (auto &x : st) {
        s.insert({0, x});
    }
    double ans = INF;
    for (int it = 0; it <= k; it++) {
        while (s.size() > 0) {
            int i = ((s.begin()))->second;
            if (dist[it][i] <= ((s.begin())->first)) {
                s.erase(s.begin());
                continue;
            }
            dist[it][i] = ((s.begin())->first);
            s.erase(s.begin());
            for (auto &x : gr[i]) {
                s.insert({dist[it][i] + x.second, x.first});
            }
        }
        ans = min(ans, dist[it][h]);
        if (it < k) {
            for (int i = 0; i < n; i++) {
                if (arr[i] == 2) {
                    for (auto &x : gr[i]) {
                        s.insert({dist[it][i] / 2 + x.second, x.first});
                    }
                }
            }
            if (arr[h] == 2) {
                ans = min(ans, dist[it][h] / 2);
            }
        }
    }
    return ans;
}

• 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