Submission #1197577

#TimeUsernameProblemLanguageResultExecution timeMemory
1197577nouka28Cyberland (APIO23_cyberland)C++20
0 / 100
35 ms20352 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>>; 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]){ cout<<-1<<endl; return 0; } } K=min(K,50); vector<vector<double>> d(K+1,vector<double>(N,1e18)); pqmin<tuple<double,int,int>> pq; d[0][0]=0;pq.push({0,0,0}); rng(i,1,N){ if(flg[i]&&arr[i]==0){ d[0][i]=0; pq.push({0,0,i}); } } while(pq.size()){ auto[cost,k,p]=pq.top();pq.pop(); for(auto&&[e,c]:g[p]){ if(d[k][e]>cost+c){ d[k][e]=cost+c; pq.push({d[k][e],k,e}); } // if(arr[e]==2&&k<K){ // double t=(cost+c)/double(2.0); // if(d[k+1][e]>t){ // d[k+1][e]=t; // pq.push({d[k+1][e],k+1,e}); // } // } } } double ans=1e18; rep(i,K+1)ans=min(ans,d[i][H]); if(ans>1e17)return -1; else 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...