제출 #751014

#제출 시각아이디문제언어결과실행 시간메모리
751014Gurban사이버랜드 (APIO23_cyberland)C++17
97 / 100
3070 ms11872 KiB
#include "cyberland.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const double inf = 1e16; const int maxn=1e5+5; const double eps = 0.00000001; int D[maxn]; vector<pair<int,double>>E[maxn]; int p[maxn]; int ata(int x){ if(p[x] == x) return x; return p[x] = ata(p[x]); } void un(int x,int y){ int aa = ata(x); int bb = ata(y); p[bb] = aa; } bool con(int x,int y){ int aa = ata(x); int bb = ata(y); return (aa == bb); } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { for(int i = 0;i < N;i++) E[i].clear(),p[i] = i; for(int i = 0;i < M;i++){ E[x[i]].push_back({y[i],c[i]}); E[y[i]].push_back({x[i],c[i]}); if(x[i] != H and y[i] != H) un(x[i],y[i]); } vector<int>zeros = {0}; vector<int>two; for(int i = 1;i < N;i++) if(arr[i] == 0 and con(0,i)) zeros.push_back(i); for(int i = 1;i < N;i++) if(arr[i] == 2) two.push_back(i); priority_queue<pair<double,int>>q; q.push({0,H}); double ans = inf; double der = 1; for(int i = 0;i <= K;i++){ vector<double>dis(N,inf); vector<bool>vis(N,0); while(!q.empty()){ int x = q.top().second; double len = -q.top().first; q.pop(); if(vis[x]) continue; vis[x] = 1; for(auto j : E[x]){ if(j.first == H) continue; double now = (j.second / der) + len; if(dis[j.first] > now){ dis[j.first] = now; q.push({-now,j.first}); } } } for(auto j : zeros) ans = min(ans,dis[j]); for(auto j : two) if(abs(dis[j] - inf) >= eps) q.push({-dis[j],j}); der *= 2; } if(abs(ans - inf) < eps) return -1; return 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...