//#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv
typedef long long ll;
typedef double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define Mp make_pair
#define sep ' '
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define kill(res) cout << res << '\n', exit(0);
#define set_dec(x) cout << fixed << setprecision(x);
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll K = 72;
const ll N = 1e5 + 50;
const ll inf = 1e18;
ll n, m, k, H, a[N];
ld dist[N][K];
bool mark[N];
vector<pll> adj[N];
void dfs(int v){
mark[v] = true;
for(auto [u, w]: adj[v]) if(!mark[u]) dfs(u);
}
void dijk(){
for(int i = 0; i < n; i++) for(int j = 0; j <= k; j++) dist[i][j] = inf;
priority_queue<pair<pair<int, ld>, int>, vector<pair<pair<int, ld>, int>>, greater<pair<pair<int, ld>, int>>> pq;
for(int i = 0; i < n; i++) if(!a[i] && mark[i]){
dist[i][0] = 0; pq.push({{0, dist[i][0]}, i});
}
while (!pq.empty()){
auto [id, vd] = pq.top().F;
auto v = pq.top().S;
pq.pop();
if(vd != dist[v][id]) continue;
if(id < k){
if(dist[v][id+1] > dist[v][id]){
dist[v][id+1] = dist[v][id];
pq.push({{id+1, dist[v][id+1]}, v});
}
}
if(v == H) continue;
for (auto [u, w]: adj[v]){
if(dist[u][id] > dist[v][id] + w){
dist[u][id] = dist[v][id] + w;
pq.push({{id, dist[u][id]}, u});
}
if(a[u] != 2 || id == k) continue;
if(dist[u][id+1] * 2 > dist[v][id] + w){
dist[u][id+1] = dist[v][id] + w; dist[u][id+1] /= 2;
pq.push({{id+1, dist[u][id+1]}, u});
}
}
}
}
void dijk2(){
for(int i = 0; i < n; i++) for(int j = 0; j <= k; j++) dist[i][j] = inf;
priority_queue<pair<ld, pii>, vector<pair<ld, pii>>, greater<pair<ld, pii>>> pq;
for(int i = 0; i < n; i++) if(i != H && mark[i]){
dist[i][0] = 0; pq.push({dist[i][0], {i, 0}});
}
while (!pq.empty()){
auto [v, id] = pq.top().S;
auto vd = pq.top().F;
pq.pop();
if(vd != dist[v][id]) continue;
if(v == H) continue;
for (auto [u, w]: adj[v]){
if(dist[u][id] > dist[v][id] + w){
dist[u][id] = dist[v][id] + w;
pq.push({dist[u][id], {u, id}});
}
if(a[u] != 2 || id == k) continue;
if(dist[u][id+1] * 2 > dist[v][id] + w){
dist[u][id+1] = dist[v][id] + w; dist[u][id+1] /= 2;
pq.push({dist[u][id+1], {u, id+1}});
}
}
}
}
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){
n = N; m = M; k = K; H = H_;
return n * m;
for(int i = 0; i < n; i++){
adj[i].clear(); mark[i] = false;
}
for(int i = 0; i < m; i++){
int u = x[i];
int v = y[i];
int w = c[i];
adj[u].pb({v, w});
adj[v].pb({u, w});
}
for(int i = 0; i < n; i++) a[i] = arr[i];
dfs(0);
if(!mark[H]) return -1;
k = min(k, 70ll);
a[0] = 0; dijk();
ld res = dist[H][k];
/*
if(K > k){
k++; dijk2();
res = min(res, dist[H][k]);
}
*/
if(res >= inf) return -1;
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
12 ms |
4748 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
4804 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
4696 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
18 ms |
6492 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
4700 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
4840 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
4696 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
4696 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |