Submission #1202608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202608		Almonther	Cyberland (APIO23_cyberland)	C++20	5 / 100	926 ms	22084 KiB

cyberland

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define co cout<<
// stuff

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int>y, std::vector<int> c, std::vector<int> arr){
    K=min(K,70);
    double vis[N+5][K+5]={};
    double ans=1e9;
    for(int i=0;i<=N;i++) for(int j=0;j<=K;j++) vis[i][j]=ans;
    vector<pair<double,int>>v[N+5];
    for(int i=0;i<M;i++){
        v[x[i]].push_back({c[i],y[i]});
        v[y[i]].push_back({c[i],x[i]});
    }
    priority_queue<pair<double,int>>q[K+5];
    q[K].push({0,0});
    for(int i=K;i>=0;i--){
        while(q[i].size()){
            auto[wei,idx]=q[i].top();
            wei=-wei;
            q[i].pop();
            if(vis[idx][i]<=wei) continue;
            vis[idx][i]=wei;
            if(idx==H){
                ans=min(ans,wei);
                continue;
            }
            for(auto[wei1,idx1]:v[idx]){
                if(arr[idx]==0) q[i].push({-wei1,idx1});
                else if(arr[idx]==2&&i>0) q[i-1].push({-(wei/2+wei1),idx1});
                q[i].push({-(wei+wei1),idx1});
            }
        }
    }
    if(ans==1e9) return -1;
    return ans;
}

• Subtask 1: 5 / 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