Submission #1232846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232846		ASGA_RedSea	Cyberland (APIO23_cyberland)	C++20	97 / 100	3094 ms	90220 KiB

cyberland

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"


#pragma GCC optimize("Ofast")





#include<bits/stdc++.h>


using namespace std;
using ll=long long;

#include "cyberland.h"


using ld=long double;
const ld eps=1e-10;


struct tp{
    ld v;
    tp(ld vl=0){v=vl;}
};

bool operator>(const tp&a,const tp&b){
    return (a.v-b.v>eps);
}
bool operator<(const tp&a,const tp&b){
    return (b>a);
}
bool operator==(const tp&a,const tp&b){
    return (abs(a.v-b.v)<eps);
}
bool operator<=(const tp&a,const tp&b){
    return (a<b)||(a==b);
}
bool operator>=(const tp&a,const tp&b){
    return (a>b)||(a==b);
}



double solve(int n,int m,int k,int h,vector<int>x,vector<int>y,vector<int>c,vector<int>arr){
    vector<vector<array<int,2>>>a(n);
    while(m--){
        int u=x[m],v=y[m],w=c[m];
        a[u].push_back({v,w});
        a[v].push_back({u,w});
    }
    k=min(k,70);

    priority_queue<pair<tp,pair<int,int>>,vector<pair<tp,pair<int,int>>>,greater<pair<tp,pair<int,int>>>>q;

    vector<vector<tp>>d(n,vector<tp>(k+1));
    for(auto&i:d)for(auto&j:i)j.v=1e18;


    cout<<fixed<<setprecision(6);

    q.push({tp(),{k,0}});
    d[0][k]=0;
    while(!q.empty()){
        tp w=q.top().first;
        int i=q.top().second.second;
        int kk=q.top().second.first;


        q.pop();

        if(d[i][kk]<w||i==h)continue;


        for(auto&[j,ww]:a[i]){
            if(arr[j]==0){
                if(d[j][kk].v>eps){
                    d[j][kk].v=0;
                    q.push({tp(),{kk,j}});
                }
            }
            if(arr[j]==2&&kk>0){
                if(d[j][kk-1].v-((ww+w.v)/2.000000000)>eps){
                    d[j][kk-1].v=(ww+w.v)/2.000000000;
                    q.push({d[j][kk-1],{kk-1,j}});
                }
            }

            if(d[j][kk].v>(ww+w.v)>eps){
                d[j][kk].v=ww+w.v;
                q.push({d[j][kk],{kk,j}});
            }
        }
    }

    ld ans=1e18;
    for(auto&i:d[h])ans=min(ans,i.v);

    return (abs(ans-1e18)<eps?-1:ans);
}






//signed main(){
//    ios_base::sync_with_stdio(0);cin.tie(0);
//
//
//    ;
//
//
//    return 0;
//}

• 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: 0 / 3