Submission #982207

#	Time	Username	Problem	Language	Result	Execution time	Memory
982207		Seb	Cyberland (APIO23_cyberland)	C++17	0 / 100	106 ms	18252 KiB

cyberland

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

using ll = long long;
using lld = double;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vii = vector<int>;
using pdi = pair<pair<long double, int>, int>;
#define pb push_back
#define MP make_pair
#define f first
#define s second

const long double INFd = (long double)1e5;

void dfs(int nodo, vector<vpii> &g, vii &arr, vector <long 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<vpii> &g, vector <long double> &ans) {
    priority_queue<pair<long double, int>, vector<pair<long double, int>>, greater<pair<long 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) 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;
}

void dijkstra(int N, int H, vector<vpii> &g, vii &arr, vector<long double> &ans) {
    priority_queue<pdi, vector<pdi>, greater<pdi>> pq;
    bool vis[N + 1][2];
    for (int i = 0; i <= N; i++)
        vis[i][0] = vis[i][1] = false;
    vis[H][0] = vis[H][1] = true;

    djks(N, H, g, ans);

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

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

        vis[p.s][p.f.s] = true;
        ans[p.s] = min(ans[p.s], p.f.f);

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

        if (p.f.s == 0) for (auto &it : g[p.s]) {
            if (arr[it.f] != 2 || vis[it.f][1]) continue;
            pq.push(MP(MP((long double)((it.s + p.f.f)/2), 1), 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<vpii> 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 <long double> ans(N + 1, INFd);
    vis[H] = true;
    dfs(0, g, arr, ans, vis);
    ans[0] = 0;

    long double ANS = INFd, preANS = -1;
    for (int i = 0; i < K; i++) {
        if (ANS == preANS) break;
        dijkstra(N, H, g, arr, ans);
        preANS = ANS;
        for (auto &it : g[H])
            ANS = min(ANS, it.s + ans[it.f]);
    }

    return ANS;
}
/*
int main() {

vii x = {1, 2}, y = {2, 0}, c = {12, 4}, arr = {1, 2, 1};
cout << solve(3, 2, 30, 2, x,y,c,arr);


}*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3