| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1200298 | crispxx | Cyberland (APIO23_cyberland) | C++20 | 0 ms | 0 KiB |
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'
#include "stub.cpp"
struct DSU {
int n; vector<int> p, sz;
DSU(int n) : p(n), sz(n, 1) {
iota(all(p), 0);
}
int find(int v) {
return v == p[v] ? v : p[v] = find(p[v]);
}
bool unite(int u, int v) {
u = find(u), v = find(v);
if(u == v) return false;
if(sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
return true;
}
};
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> a) {
vector<vector<ar<int, 2>>> adj(n);
DSU dsu(n);
for(int i = 0; i < m; i++) {
adj[x[i]].pb({y[i], c[i]});
adj[y[i]].pb({x[i], c[i]});
if(x[i] != h && y[i] != h) {
dsu.unite(x[i], y[i]);
}
}
K = min(K, 70);
vector d(n, vector<long double>(K + 1, 1e18));
priority_queue<pair<long double, int>, vector<pair<long double, int>>, greater<>> pq;
pq.emplace(d[0][0] = 0, 0);
for(int i = 0; i < n; i++) {
if(a[i] == 0 && dsu.find(0) == dsu.find(i)) {
pq.emplace(d[i][0] = 0, i);
}
}
long double ans = 1e18;
for(int k = 0; k < K; k++) {
priority_queue<pair<long double, int>, vector<pair<long double, int>>, greater<>> nxt;
while(!pq.empty()) {
auto [d_v, v] = pq.top();
pq.pop();
if(d_v != d[v][k]) continue;
if(v == h) {
ans = min(ans, d[v][k]);
continue;
}
for(auto [to, c] : adj[v]) {
if(d[to][k] > d[v][k] + c) {
pq.emplace(d[to][k] = d[v][k] + c, to);
}
if(a[to] == 2 && d[to][k + 1] > (d[v][k] + c) / 2.0) {
nxt.emplace(d[to][k + 1] = (d[v][k] + c) / 2.0, to);
}
}
}
swap(pq, nxt);
}
return ans > 1e17 ? -1 : ans;
}