Submission #1127347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127347		psm9352	Cyberland (APIO23_cyberland)	C++20	49 / 100	561 ms	70200 KiB

cyberland

#include <vector>
#include <queue>
#include <tuple>

using namespace std;

template <typename T>
using min_heap = priority_queue<T,vector<T>,greater<T>>;

double solve(int n, int m, int k, int h, vector<int> x, vector<int>y, vector<int> c, vector<int> arr){
    k = min(k,75);
    vector<vector<double>> ans(k+1,vector<double>(n,1e18));
    vector<vector<pair<int,double>>> graph(n);
    for (int i = 0;i < m;i++){
        graph[x[i]].push_back({y[i],c[i]});
        graph[y[i]].push_back({x[i],c[i]});
    }
    min_heap<tuple<int,double,int>> pq;
    pq.push({0,0,0});
    ans[0][0]=0;
    while(!pq.empty()){
        const auto [ck,cdist,node] = pq.top();pq.pop();
        if (node==h){continue;}
        if (ans[ck][node] < cdist){continue;}
        
        for (const auto &[next,weight]:graph[node]){
            if (arr[next]==0){
                if (0 < ans[ck][next]){
                    ans[ck][next]=0;
                    pq.push({0,0,next});
                }
            }
            if (cdist+weight < ans[ck][next]){
                ans[ck][next]=(cdist+weight);
                pq.push({ck,(cdist+weight),next});
            }
            if (arr[next]==2){
                if (ck < k){
                    if ((cdist+weight)/2 < ans[ck][next]){
                        ans[ck][next]=(cdist+weight)/2;
                        pq.push({ck+1,(cdist+weight)/2,next});
                    }
                }
            }
        }
        
    }
    double fans = 1e18;
    for (int i = 0;i<=k;i++){
        fans = min(fans,ans[i][h]);
    }
    if (fans>=1e18){return -1;}
    return fans;
}

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