Submission #1202011

#TimeUsernameProblemLanguageResultExecution timeMemory
1202011ASGA_RedSeaCyberland (APIO23_cyberland)C++20
49 / 100
49 ms10564 KiB
/** * بسم الله الرحمن الرحيم * ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿ */ /// 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}); } priority_queue<pair<tp,pair<int,int>>,vector<pair<tp,pair<int,int>>>,greater<pair<tp,pair<int,int>>>>q; vector<tp>d(n); for(auto&i:d)i.v=1e18; q.push({tp(),{k,0}}); d[0]=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]<w||i==h)continue; for(auto&[j,ww]:a[i]){ if(arr[j]==0){ if(d[j].v>eps){ d[j].v=0; q.push({tp(),{kk,j}}); } } if(arr[j]==2&&kk>0){ if(d[j].v-((ww+w.v)/2.000000000)>eps){ d[j].v=(ww+w.v)/2.000000000; q.push({d[j],{kk-1,j}}); } } if(d[j].v>(ww+w.v)>eps){ d[j].v=ww+w.v; q.push({d[j],{kk,j}}); } } } ld ans=d[h].v; return (abs(ans-1e18)<eps?-1:ans); } //signed main(){ // ios_base::sync_with_stdio(0);cin.tie(0); // // // ; // // // return 0; //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...