제출 #1228081

#제출 시각아이디문제언어결과실행 시간메모리
1228081peraCyberland (APIO23_cyberland)C++20
68 / 100
3095 ms89156 KiB
#include "cyberland.h" #include <bits/stdc++.h> #define LL __int128 using namespace std; const int N = 1E5 + 1 , W = 65; LL dist[N][W] , P[W]; 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(); } P[0] = 1; for(int i = 1;i < W;i ++){ P[i] = P[i - 1] * (LL)2; } for(int i = 0;i < N;i ++){ for(int j = 0;j <= K;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 , 64); priority_queue<pair<LL , pair<int , int>>> pq; dist[0][0] = 0; LL ans = -1; int p = 0; pq.push(pair<LL , pair<int , int>>{0 , pair<int , int>{0 , 0}}); while(!pq.empty()){ auto [D , V] = pq.top(); auto [u , x] = V; pq.pop(); if(dist[u][x] != D){ continue; } if(u == H){ if(ans == -1){ ans = dist[H][x]; p = x; continue; } LL left = ans * P[x]; LL right = dist[H][x] * P[p]; if(right < left){ ans = dist[H][x]; p = x; } continue; } for(auto [v , w] : g[u]){ LL nD = D + w * P[x]; if(arr[v] == 0){ nD = 0; } if(dist[v][x] == -1 || dist[v][x] > nD){ dist[v][x] = nD; pq.push(pair<LL , pair<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(pair<LL , pair<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...