제출 #879147

#제출 시각아이디문제언어결과실행 시간메모리
879147leanchec사이버랜드 (APIO23_cyberland)C++17
63 / 100
3039 ms143192 KiB
#include "cyberland.h" #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include<bits/stdc++.h> using namespace std; vector<pair<int,int>> adj[100100]; bool visited[100100]; void dfs(int cur, int H){ visited[cur]=true; for(int i=0; i<(int)adj[cur].size(); i++){ int viz=adj[cur][i].first; int w=adj[cur][i].second; if(viz==H){ adj[H].push_back({cur, w}); continue; } if(visited[viz])continue; dfs(viz, H); } } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){ for(int i=0; i<N; i++){ visited[i]=0; adj[i].clear(); } for(int i=0; i<M; i++){ if(x[i]!=H)adj[x[i]].push_back({y[i], c[i]}); if(y[i]!=H)adj[y[i]].push_back({x[i], c[i]}); } K=min(K, 70); dfs(0, H); long double dist[100100][75], po[74]; bool achou[100100][75]; po[0]=1; for(int i=1; i<=K; i++)po[i]=po[i-1]*2; for(int i=0; i<N; i++){ for(int j=0; j<=K; j++){ dist[i][j]=1e15; achou[i][j]=0; } } priority_queue<pair<long double, pair<int, int>>, vector<pair<long double, pair<int,int>>>, greater<pair<long double, pair<int,int>>>> pq; pq.push({0, {H, 0}}); dist[H][0]=0; while(!pq.empty()){ pair<long double, pair<int,int>> curtop=pq.top(); pq.pop(); int cur=curtop.second.first; int curk=curtop.second.second; if(cur==0 || arr[cur]==0 || curk==K){ return dist[cur][curk]; } if(achou[cur][curk])continue; achou[cur][curk]=true; for(int i=0; i<(int)adj[cur].size(); i++){ int viz=adj[cur][i].first; if(viz==H)continue; long double w=adj[cur][i].second; if(arr[cur]==2){ w/=po[curk+1]; if(dist[viz][curk+1]>dist[cur][curk]+w){ dist[viz][curk+1]=dist[cur][curk]+w; pq.push({dist[viz][curk+1], {viz, curk+1}}); } } else if(dist[viz][curk]>dist[cur][curk]+w/po[curk]){ w/=po[curk]; dist[viz][curk]=dist[cur][curk]+w; pq.push({dist[viz][curk], {viz, curk}}); } } } return -1; }
#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...