This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> fa, sz;
dsu(int n) {
fa.resize(n + 10);
iota(fa.begin(), fa.end(), 0);
sz.assign(n + 10, 1);
}
int find(int x) {
while (x != fa[x]) x = fa[x] = fa[fa[x]];
return x;
}
bool merge(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
if (sz[py] > sz[px]) swap(px, py);
sz[px] += sz[py]; fa[py] = px;
return true;
}
bool same(int x, int y) {
int px = find(x), py = find(y);
return px == py;
}
};
#include "cyberland.h"
#define ld long double
double solve(int N, int M, int K, int H, vector<int> fir, vector<int> sec, vector<int> co, vector<int> arr) {
K = min(K, 69);
vector<vector<pair<int,int>>> g(N);
dsu ds(N);
for (int i = 0; i < M; i++) {
if (fir[i] != H && sec[i] != H) ds.merge(fir[i], sec[i]);
g[fir[i]].push_back(make_pair(co[i], sec[i]));
g[sec[i]].push_back(make_pair(co[i], fir[i]));
}
vector<ld> pwr(K + 1, 1);
for (int i = 1; i <= K; i++) {
pwr[i] = pwr[i - 1] / 2;
}
arr[0] = 0;
vector<vector<ld>> dist(K + 1, vector<ld>(N, 1e18));
using node = tuple<ld, int, int>;
priority_queue<node, vector<node>, greater<node>> pq;
auto enq = [&](int k, int x, ld d) {
if (dist[k][x] > d) {
dist[k][x] = d;
pq.push({ d,k,x });
}
};
enq(K, H, 0);
while (pq.size()) {
auto [d, k, x] = pq.top(); pq.pop();
if (dist[k][x] < d) continue;
if (arr[x] == 0) return (double)d;
for (auto& [c, v] : g[x]) {
if (ds.find(v) != ds.find(0)) continue;
enq(k, v, d + c * pwr[K - k]);
if (arr[x] == 2 && k > 0) enq(k - 1, v, d + c * pwr[K - k + 1]);
}
}
return (double)-1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |