Submission #1253936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253936		anfi	Cyberland (APIO23_cyberland)	C++20	0 / 100	66 ms	7352 KiB

cyberland

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const double inf = 1e18;

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
    double ans = 1e18;
    K = min(K, 100);
    vector<pair<int,int>> adj[N];
    vector<double> dp(N, inf), tmp(N, inf);
    for(int i = 0;i < M; i++){
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }
    priority_queue<pair<double, int>> pq;
    tmp[0] = 0.0;
    for(int i = 0; i <= K; i++){
        if(i){
            for(int j = 0; j < N; j++){
                if(arr[i] == 1 || dp[i] == inf) continue;
                if(arr[i] == 0) tmp[i] = 0.0;
                pq.push({-dp[i]/2.0, i});
            }
        }else pq.push({0.0, 0});

        while(!pq.empty()){
            auto [c, u] = pq.top(); pq.pop();
            c = -c;
            if(u == H) continue;
            if(c > dp[u]) continue;
            for(auto &[v, w] : adj[u]){
                double cost = c+w;
                if(tmp[v] > cost){
                    if(arr[i] == 0) tmp[v] = 0.0;
                    else tmp[v] = cost;
                    pq.push({-tmp[v], v});
                }          
            }
        }
        ans = min(ans, tmp[H]);
        if(i == 0 && tmp[H]== inf) break;
        swap(tmp, dp);
    }
    return (ans >= inf/2 ? -1.0 :ans);
}

• 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