Submission #1197602

#TimeUsernameProblemLanguageResultExecution timeMemory
1197602nouka28사이버랜드 (APIO23_cyberland)C++20
15 / 100
3109 ms526352 KiB
#include "cyberland.h" #include <vector> #include<bits/stdc++.h> using namespace std; // #include<atcoder/all> // using namespace atcoder; // using mint=atcoder::modint998244353; // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") // #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define rng(i,l,r) for(int i=(l);i<(r);i++) #define rrep(i,n) for(int i=(n)-1;i>=0;i--) #define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--) #define fi first #define se second #define all(x) (x).begin(),(x).end() // struct fast_io{fast_io(){std::cin.tie(nullptr)->sync_with_stdio(false);}}_; template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>; using lint=__int128_t; 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) { vector<vector<pair<int,int>>> g(N); rep(i,M){ g[x[i]].push_back({y[i],c[i]}); g[y[i]].push_back({x[i],c[i]}); } vector<bool> flg(N); { stack<int> q; q.push(0); while(q.size()){ int p=q.top();q.pop(); flg[p]=1; for(auto&&[e,c]:g[p]){ if(flg[e])continue; q.push(e); } } if(!flg[H]){ return -1; } } K=min(K,50); vector<vector<lint>> d(K+1,vector<lint>(N,lint(1)<<120)); pqmin<tuple<lint,int,int>> pq; rep(i,N){ if(i==0||arr[i]==0){ d[0][i]=0; pq.push({0,0,i}); } } while(pq.size()){ auto[cost,k,p]=pq.top();pq.pop(); if(d[k][p]<cost)continue; for(auto&&[e,c]:g[p]){ lint nc=cost+(lint(c)<<k); if(d[k][e]>cost+c){ d[k][e]=nc; pq.push({nc,k,e}); } if(arr[e]==2&&k<K){ if(d[k+1][e]>cost){ d[k+1][e]=d[k][e]; pq.push({d[k][e],k+1,e}); } } } } double ans=1e18; rep(i,K+1){ long double t=(long double)(d[i][H])/(long double)(lint(1)<<i); if(ans>t)ans=t; } return ans; }
#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...