Submission #1127281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127281		psm9352	Cyberland (APIO23_cyberland)	C++20	0 / 100	158 ms	20604 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,69);
    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});
    vector<bool> visited(n,0);
    queue<int> q;q.push(0);
    while (!q.empty()){
        int node = q.front();q.pop();
        if (visited[node]){continue;}
        visited[node]=1;
        for (auto [next,weight]:graph[node]){if(next==h)continue;q.push(next);}
    }
    for (int i = 1;i<n;i++){if (arr[i]==0 and visited[i]){pq.push({0,0,i});}}
    for (int i = 0;i<=k;i++){
        ans[i][0]=0;
        for (int node = 1;node < n;node++){
            if (arr[node]==0 and visited[node]){ans[i][node]=0;}
        }
    }
    while(!pq.empty()){
        const auto &[ck,cdist,node] = pq.top();pq.pop();
        if (arr[node]==h){return ans[ck][node];}
        if (ans[ck][node] < cdist){continue;}
        for (const auto &[next,weight]:graph[node]){
            if (arr[next]==1){
                if (cdist+weight < ans[ck][next]){
                    ans[ck][next]=cdist+weight;
                    pq.push({ck,cdist+weight,next});
                }
            }else{
                if (ck < k and (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: 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