Submission #750485

#TimeUsernameProblemLanguageResultExecution timeMemory
750485arnold518Cyberland (APIO23_cyberland)C++17
8 / 100
74 ms24756 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; const double INF = 1e18; const double eps = 1e-10; int N, M, K, H, A[MAXN+10]; vector<pii> adj[MAXN+10]; double dist[MAXN+10][40], P[40]; struct Queue { int v, k; double w; bool operator < (const Queue &p) const { return w>p.w; } }; 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) { N=_N; M=_M; K=_K; H=_H+1; for(int i=1; i<=N; i++) A[i]=_arr[i-1]; for(int i=0; i<M; i++) { int u=_x[i]+1, v=_y[i]+1, w=_c[i]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } K=min(K, 30); for(int i=1; i<=N; i++) for(int j=0; j<=K; j++) dist[i][j]=INF; priority_queue<Queue> PQ; dist[H][0]=0; PQ.push({H, 0, 0}); P[0]=1; for(int i=1; i<=K; i++) P[i]=P[i-1]/2; while(!PQ.empty()) { Queue now=PQ.top(); PQ.pop(); if(fabs(dist[now.v][now.k]-now.w)>eps) continue; //printf("%d %d %.10lf\n", now.v, now.k, now.w); if(A[now.v]==0) continue; if(A[now.v]==2) { for(auto nxt : adj[now.v]) { if(now.w+P[now.k+1]*nxt.second<dist[nxt.first][now.k+1]) { dist[nxt.first][now.k+1]=now.w+P[now.k+1]*nxt.second; PQ.push({nxt.first, now.k+1, now.w+P[now.k+1]*nxt.second}); } } } else { for(auto nxt : adj[now.v]) { if(now.w+P[now.k]*nxt.second<dist[nxt.first][now.k]) { dist[nxt.first][now.k]=now.w+P[now.k]*nxt.second; PQ.push({nxt.first, now.k, now.w+P[now.k]*nxt.second}); } } } } double ans=INF; for(int i=1; i<=N; i++) { adj[i].clear(); for(int j=0; j<=K; j++) { if(A[i]==0 || i==1) ans=min(ans, dist[i][j]); dist[i][j]=0; } } if(ans==-1) ans=0; 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...