//#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 long 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 = 100;
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;
dist[0][0] = 0; pq.push({{0, 0}, 0});
while (!pq.empty()){
auto [id, vd] = pq.top().F;
auto v = pq.top().S;
pq.pop();
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;
if(a[u] == 0) dist[u][id] = 0;
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<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(i != H && mark[i] && a[i] != 1){dist[i][0] = 0; pq.push({{0, 0}, i});}
while (!pq.empty()){
auto [id, vd] = pq.top().F;
auto v = pq.top().S;
pq.pop();
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;
if(a[u] == 0) dist[u][id] = 0;
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});
}
}
}
}
double solve(int N, int M, int Kk, int H_, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
n = N; m = M; k = Kk; H = H_;
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(Kk > k){
dijk2();
res = min(res, dist[H][k]);
}
if(res >= inf) return -1;
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
4700 KB |
Correct. |
2 |
Correct |
35 ms |
4700 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
227 ms |
4944 KB |
Correct. |
2 |
Correct |
284 ms |
5464 KB |
Correct. |
3 |
Correct |
264 ms |
5004 KB |
Correct. |
4 |
Correct |
274 ms |
4916 KB |
Correct. |
5 |
Correct |
274 ms |
5200 KB |
Correct. |
6 |
Correct |
321 ms |
21060 KB |
Correct. |
7 |
Correct |
387 ms |
21000 KB |
Correct. |
8 |
Correct |
169 ms |
38868 KB |
Correct. |
9 |
Correct |
207 ms |
5040 KB |
Correct. |
10 |
Correct |
193 ms |
4696 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
273 ms |
5000 KB |
Correct. |
2 |
Correct |
277 ms |
5236 KB |
Correct. |
3 |
Correct |
246 ms |
5012 KB |
Correct. |
4 |
Correct |
207 ms |
4780 KB |
Correct. |
5 |
Correct |
206 ms |
4696 KB |
Correct. |
6 |
Correct |
68 ms |
18520 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
216 ms |
102476 KB |
Correct. |
2 |
Correct |
240 ms |
4996 KB |
Correct. |
3 |
Correct |
187 ms |
5036 KB |
Correct. |
4 |
Correct |
204 ms |
5264 KB |
Correct. |
5 |
Correct |
147 ms |
4700 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
105 ms |
4948 KB |
Correct. |
2 |
Correct |
128 ms |
5072 KB |
Correct. |
3 |
Correct |
120 ms |
5228 KB |
Correct. |
4 |
Correct |
147 ms |
20752 KB |
Correct. |
5 |
Correct |
74 ms |
4696 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
136 ms |
5088 KB |
Correct. |
2 |
Correct |
89 ms |
4984 KB |
Correct. |
3 |
Correct |
32 ms |
11600 KB |
Correct. |
4 |
Correct |
91 ms |
14636 KB |
Correct. |
5 |
Correct |
90 ms |
4788 KB |
Correct. |
6 |
Correct |
107 ms |
4984 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
5024 KB |
Correct. |
2 |
Correct |
33 ms |
5172 KB |
Correct. |
3 |
Correct |
1355 ms |
168400 KB |
Correct. |
4 |
Correct |
717 ms |
42652 KB |
Correct. |
5 |
Correct |
675 ms |
70676 KB |
Correct. |
6 |
Correct |
299 ms |
26580 KB |
Correct. |
7 |
Correct |
661 ms |
47164 KB |
Correct. |
8 |
Correct |
529 ms |
9772 KB |
Correct. |
9 |
Correct |
159 ms |
5176 KB |
Correct. |
10 |
Correct |
138 ms |
5088 KB |
Correct. |
11 |
Correct |
477 ms |
7260 KB |
Correct. |
12 |
Correct |
171 ms |
4952 KB |
Correct. |
13 |
Correct |
172 ms |
5144 KB |
Correct. |
14 |
Correct |
601 ms |
84928 KB |
Correct. |
15 |
Correct |
573 ms |
26208 KB |
Correct. |
16 |
Correct |
154 ms |
4952 KB |
Correct. |
17 |
Correct |
194 ms |
5120 KB |
Correct. |
18 |
Correct |
171 ms |
5140 KB |
Correct. |
19 |
Correct |
444 ms |
5060 KB |
Correct. |
20 |
Correct |
11 ms |
4700 KB |
Correct. |
21 |
Correct |
12 ms |
4700 KB |
Correct. |
22 |
Correct |
25 ms |
5660 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
789 ms |
4944 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |