Submission #896285

#TimeUsernameProblemLanguageResultExecution timeMemory
896285dostsCyberland (APIO23_cyberland)C++17
15 / 100
42 ms7256 KiB
#pragma GCC optimize("O3,unroll-loops") #include "cyberland.h" #include <bits/stdc++.h> using namespace std; vector<pair<int,int>> edges[100000]; 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++) edges[i].clear(); for (int i=0;i<M;i++) { edges[x[i]].push_back({y[i],c[i]}); edges[y[i]].push_back({x[i],c[i]}); } double dp[N][2]; for (int i=0;i<N;i++) { for (int j=0;j<2;j++) dp[i][j] = 2e18; } using wtf = pair<double,pair<int,int>>; priority_queue<wtf,vector<wtf>,greater<wtf>> pq; pq.push({0,{0,0}}); pq.push({0,{0,1}}); while (!pq.empty()) { wtf f = pq.top(); pq.pop(); double cost = f.first; int used = f.second.second; int city = f.second.first; if (dp[city][used] <= cost) continue; dp[city][used] = cost; for (auto it : edges[city]) { int dest = it.first; int go = it.second; if (!arr[dest]) { pq.push(make_pair(0,make_pair(dest,used))); } else if (arr[dest]) { pq.push({cost+go,{dest,used}}); } else { if (!used) pq.push({(cost+go)/pow(2,K),{dest,1}}); pq.push({cost+go,{dest,used}}); } } } return dp[H][1]==2e18?-1:dp[H][1]; }
#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...