Submission #982321

#	Time	Username	Problem	Language	Result	Execution time	Memory
982321		Seb	Cyberland (APIO23_cyberland)	C++17	100 / 100	2356 ms	24088 KiB

cyberland

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

using ll = long long;
using lld = double;
using pid = pair<int, double>;
using vpid = vector<pid>;
using vii = vector<int>;

#define pb push_back
#define MP make_pair
#define f first
#define s second

const double INFd = (double)1e15;

void dfs(int nodo, vector<vpid> &g, vii &arr, vector <double> &ans, vector <bool> &vis) {
    if (arr[nodo] == 0) ans[nodo] = 0;
    vis[nodo] = true;
    for (auto &it : g[nodo]) {
        if (vis[it.f]) continue;
        dfs(it.f, g, arr, ans, vis);
    }
    return;
}

void djks(int N, int H, vector<vpid> &g, vector <double> &ans, vector<bool> &VIS) {
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
    bool vis[N + 1];
    for (int i = 0; i <= N; i++) vis[i] = false;
    vis[H] = true;

    for (int i = 0; i < N; i++)
        if (i != H && VIS[i]) pq.push(MP(ans[i], i));

    while (!pq.empty()) {
        while (!pq.empty() && vis[pq.top().s]) pq.pop();
        if (pq.empty()) break;
        auto p = pq.top();
        vis[p.s] = true;
        ans[p.s] = min(ans[p.s], p.f);

        for (auto &it : g[p.s]) {
            if (vis[it.f]) continue;
            pq.push(MP(it.s + p.f, it.f));
        }
    }
    return;
}

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) {
    vector<vpid> g(N + 1);
    for (int i = 0; i < M; i++) {
        g[x[i]].pb(MP(y[i], c[i]));
        g[y[i]].pb(MP(x[i], c[i]));
    }
    vector <bool> vis(N + 1, false);
    vector <double> ans(N + 1, INFd);
    vector <double> aux(N + 1, INFd);
    vis[H] = true;
    dfs(0, g, arr, ans, vis);
    ans[0] = 0;

    K = min(K, 80);
    for (int i = 0; i < K; i++) {

        djks(N, H, g, ans, vis);

        aux = ans;
        for (int i = 0; i < N; i++)
            if (i != H && vis[i] && arr[i] == 2)
                for (auto &it : g[i])
                    if (it.f != H)
                        aux[i] = min(aux[i], (double)((it.s + ans[it.f])/2));
        for (int i = 0; i <= N; i++) ans[i] = min(ans[i], aux[i]);
    }
    djks(N, H, g, ans, vis);

    double ANS = INFd;
    for (auto &it : g[H])
            if (vis[it.f])
                ANS = min(ANS, (double)(it.s + ans[it.f]));

    if (ANS == INFd) ANS = -1;
    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