Submission #1228104

#TimeUsernameProblemLanguageResultExecution timeMemory
1228104peraCyberland (APIO23_cyberland)C++20
97 / 100
3095 ms95632 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]); } K = min(K , 74); priority_queue<pair<LL , pair<int , int>> , vector<pair<LL , pair<int , int>>> , greater<pair<LL , pair<int , int>>>> pq; dist[0][0] = 0; LL ans = -1; pq.push({0 , {0 , 0}}); while(!pq.empty()){ LL D = pq.top().first; auto [u , x] = 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(arr[v] == 0){ nD = 0; } if(dist[v][x] == -1 || dist[v][x] > nD){ dist[v][x] = nD; pq.push({dist[v][x] , {v , x}}); } 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({dist[v][x + 1] , {v , x + 1}}); } } } 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...