Submission #1228061

#TimeUsernameProblemLanguageResultExecution timeMemory
1228061peraCyberland (APIO23_cyberland)C++20
97 / 100
646 ms66116 KiB
#include "cyberland.h" #include <bits/stdc++.h> #define LL __int128 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 , LL>>> 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[0][0] = 0; LL ans = -1 , p = 0; pq.push(tuple<LL , int , int>{0 , 0 , 0}); while(!pq.empty()){ auto [D , u , x] = pq.top(); pq.pop(); if(dist[u][x] != D){ continue; } if(u == H){ if(ans == -1){ ans = dist[H][x]; p = x; continue; } LL left = ans * (1LL << x); LL right = dist[H][x] * (1LL << p); if(right < left){ ans = dist[H][x]; p = x; } continue; } for(auto [v , w] : g[u]){ LL nD = D + w * (1LL << x); if(arr[v] == 0){ nD = 0; } 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 + 1}); } } } if(ans == -1){ return ans; } long double S = 1; for(int i = 0;i < p;i ++){ S /= 2.0; } S *= (long double)ans; 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...