Submission #1127590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127590		psm9352	Cyberland (APIO23_cyberland)	C++20	100 / 100	2813 ms	13044 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){
    arr[0]=0;
    double fans = 1e18;
    k = min(k,69);
    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;
    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;
        if (arr[node]==0){pq.push({0,0,node});}
        for (const auto &[next,weight]:graph[node]){if(next==h){continue;}q.push(next);}
    }
    vector<vector<bool>> visited2(k+1,vector<bool>(n,0));
    while(!pq.empty()){
        const auto [ck,cdist,node] = pq.top();pq.pop();
        if (node==h){fans = min(fans,cdist);continue;}
        if (visited2[ck][node]){continue;}
        visited2[ck][node]=1;
        for (const auto &[next,weight]:graph[node]){
            if (!visited2[ck][next]){
                pq.push({ck,cdist+weight,next});
            }
            if (arr[next]==2){
                if (ck < k and !visited2[ck+1][next]){
                    pq.push({ck+1,(cdist+weight)/2,next});
                }
            }
        }
        
    }
    if (fans>=1e18){return -1;}
    return fans;
}

• 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