Submission #1127297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127297		psm9352	Cyberland (APIO23_cyberland)	C++20	49 / 100	141 ms	65592 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<double,int,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 (const 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 [cdist,ck,node] = pq.top();pq.pop();
        if (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({cdist+weight,ck,next});
                }
            }else if (arr[next]==2){
                if (ck < k and (cdist+weight)/2 < ans[ck][next]){
                    ans[ck][next]=(cdist+weight)/2;
                    pq.push({(cdist+weight)/2,ck+1,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