Submission #1228139

#TimeUsernameProblemLanguageResultExecution timeMemory
1228139peraCyberland (APIO23_cyberland)C++20
15 / 100
3095 ms45888 KiB
#include "cyberland.h" #include <bits/stdc++.h> #define LL double using namespace std; const int N = 1E5 + 1 , KM = 75; LL dist[N][KM]; vector<pair<int , LL>> g[N]; 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) { for(int i = 0;i < N;i ++){ g[i].clear(); for(int j = 0;j < min(K + 1 , KM);j ++){ dist[i][j] = -1; } } for(int i = 0;i < M;i ++){ g[x[i]].emplace_back(y[i] , c[i]); g[y[i]].emplace_back(x[i] , c[i]); } vector<bool> vis(N); vis[0] = true; function<void(int)> dfs = [&](int u){ for(auto [v , w] : g[u]){ if(!vis[v]){ vis[v] = true; dfs(v); } } }; dfs(0); K = min(K , 74); priority_queue<pair<int , pair<LL , int>> , vector<pair<int , pair<LL , int>>> , greater<pair<int , pair<LL , int>>>> pq; LL ans = -1; for(int i = 0;i < N;i ++){ if(vis[i] && (i == 0 || arr[i] == 0)){ pq.push({0 , {0 , i}}); dist[i][0] = 0; } } while(!pq.empty()){ int x = pq.top().first; x = -x; auto [D , u] = pq.top().second; pq.pop(); if(dist[u][x] != D){ continue; } if(u == H){ if(ans == -1){ ans = D; }else{ ans = min(ans , D); } continue; } for(auto [v , w] : g[u]){ LL nD = D + w; if(dist[v][x] == -1 || dist[v][x] > nD){ dist[v][x] = nD; pq.push({-x , {dist[v][x] , v}}); } nD /= 2.0; if(arr[v] == 2 && x < K && (dist[v][x + 1] == -1 || dist[v][x + 1] > nD)){ dist[v][x + 1] = nD; pq.push({-x - 1, {dist[v][x + 1] , v}}); } } } return (double)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...