Submission #1232255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232255		dizzy_groovy	Cyberland (APIO23_cyberland)	C++20	97 / 100	3095 ms	94520 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;

const double INF = 1e18;

void dfs(int i, vector<bool> &used, vector<vector<pair<int, double>>> &gr, int h) {
    if (used[i]) return;
    used[i] = true;
    if (i == h) return;
    for (auto &x : gr[i]) dfs(x.first, used, gr, 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--;
    if (k > 100) k = 100;
    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]});
    }
    gr[h].clear();
    vector<bool> used(n);
    dfs(0, used, gr, h);
    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);
    }
    for (auto &x : st) {
        for (int tmp = 1; tmp <= k; tmp++) {
            dist[tmp][x] = 0;
        }
    }
    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());
            if (i == h) continue;
            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 (dist[it][i] == INF) continue;
                if (i == h) continue;
                if (arr[i] == 2) {
                    for (auto &x : gr[i]) {
                        //if (arr[x.first] == 0) continue;
                        s.insert({dist[it][i] / 2 + x.second, x.first});
                    }
                }
            }
        }
    }
    assert(ans != INF);
    return ans;
}
/*
1
7 6 30
6
1 1 2 2 1 1 1
0 1 62830208
1 2 43207456
2 3 365326424
3 4 364309910
4 5 859258884
5 6 933234961
*/

• 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