Submission #753123

#	Time	Username	Problem	Language	Result	Execution time	Memory
753123		Jarif_Rahman	Cyberland (APIO23_cyberland)	C++17	100 / 100	2347 ms	23008 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
typedef long double ld;

const long double inf = 1e18;

vector<vector<pair<int, long double>>> graph;
vector<bool> reachable;

void dfs(int nd){
    if(reachable[nd]) return;
    reachable[nd] = 1;
    for(auto [x, w]: graph[nd]) dfs(x);
}

double solve(int n, int m, int k, int h, vector<int> U, vector<int> V, vector<int> C, vector<int> arr){
    k = min(k, 70);
    k++;

    graph.assign(n, {});
    vector<pair<int, long double>> edge_with_h;
    reachable.assign(n, 0);

    for(int i = 0; i < m; i++){
        if(U[i] == h || V[i] == h){
            edge_with_h.pb({U[i]+V[i]-h, C[i]});
            continue;
        }
        graph[U[i]].pb({V[i], C[i]});
        graph[V[i]].pb({U[i], C[i]});
    }

    dfs(0);

    vector<long double> dis(n, inf);
    vector<bool> bl(n, 0);
    priority_queue
    <pair<long double, int>, vector<pair<long double, int>>, greater<pair<long double, int>>> pq;

    for(int i = 0; i < n; i++) if(i == 0 || (arr[i] == 0 && reachable[i])){
        dis[i] = 0;
    }

    for(int ki = 0; ki < k; ki++){
        if(ki != 0){
            auto _dis = dis;
            for(int i = 0; i < n; i++) if(arr[i] == 2 && reachable[i]){
                if(i == h) continue;
                for(auto [x, w]: graph[i]) dis[i] = min(dis[i], (_dis[x]+w)/ld(2));
            }
        }

        bl.assign(n, 0);
        for(int i = 0; i < n; i++) if(reachable[i]) pq.push({dis[i], i});

        while(!pq.empty()){
            int nd = pq.top().sc;
            pq.pop();
            if(bl[nd]) continue;
            bl[nd] = 1;

            for(auto [x, w]: graph[nd]) if(dis[nd]+w < dis[x]){
                dis[x] = dis[nd]+w;
                pq.push({dis[x], x});
            }
        }
    }

    long double ans = inf;
    for(auto [x, w]: edge_with_h){
        ans = min(ans, dis[x]+w);
    }

    if(ans >= inf) return -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