제출 #1227980

#제출 시각아이디문제언어결과실행 시간메모리
1227980peraCyberland (APIO23_cyberland)C++20
15 / 100
27 ms21316 KiB
#include "cyberland.h" #include <bits/stdc++.h> #define LL long long using namespace std; 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); 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 , 30); vector<vector<LL>> dist(N , vector<LL>(K + 1 , -1)); priority_queue<tuple<LL , int , int> , vector<tuple<LL , int , int>> , greater<tuple<LL , int , int>>> pq; dist[H][0] = 0; pq.push(tuple<LL , int , int>{0 , H , 0}); while(!pq.empty()){ auto [D , u , x] = pq.top(); pq.pop(); 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(tuple<LL , int , int>{dist[v][x] , v , x}); } if(arr[v] == 2 && x < K && (dist[v][x + 1] == -1 || dist[v][x + 1] > nD)){ dist[v][x + 1] = nD; pq.push(tuple<LL , int , int>{dist[v][x + 1] , v , x}); } } } LL ans = -1 , p = 0; for(int i = 0;i < N;i ++){ if(i == 0 || arr[i] == 0){ for(int x = 0;x <= K;x ++){ if(dist[i][x] != -1){ if(ans == -1){ ans = dist[i][x]; p = x; continue; } LL left = ans * (1LL << x); LL right = dist[i][x] * (1LL << p); if(right < left){ ans = dist[i][x]; p = x; } } } } } if(ans == -1){ return ans; } long double S = ans; for(int i = 0;i < p;i ++){ S /= 2.0; } return (double)S; }
#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...