//#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 = 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;
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});
}
}
}
}
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){
k++; dijk2();
res = min(res, dist[H][k]);
}
*/
if(res >= inf) return -1;
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
4696 KB |
Correct. |
2 |
Correct |
36 ms |
4952 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
234 ms |
4948 KB |
Correct. |
2 |
Correct |
290 ms |
5216 KB |
Correct. |
3 |
Correct |
267 ms |
5204 KB |
Correct. |
4 |
Correct |
275 ms |
4996 KB |
Correct. |
5 |
Correct |
278 ms |
4988 KB |
Correct. |
6 |
Correct |
276 ms |
16952 KB |
Correct. |
7 |
Correct |
367 ms |
16868 KB |
Correct. |
8 |
Correct |
171 ms |
28628 KB |
Correct. |
9 |
Correct |
197 ms |
4696 KB |
Correct. |
10 |
Correct |
197 ms |
4784 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
273 ms |
5004 KB |
Correct. |
2 |
Correct |
271 ms |
5880 KB |
Correct. |
3 |
Correct |
252 ms |
5700 KB |
Correct. |
4 |
Correct |
209 ms |
5668 KB |
Correct. |
5 |
Correct |
207 ms |
5456 KB |
Correct. |
6 |
Correct |
63 ms |
14680 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
184 ms |
78028 KB |
Correct. |
2 |
Correct |
211 ms |
6012 KB |
Correct. |
3 |
Correct |
189 ms |
5976 KB |
Correct. |
4 |
Correct |
199 ms |
5872 KB |
Correct. |
5 |
Correct |
149 ms |
5660 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
104 ms |
4956 KB |
Correct. |
2 |
Correct |
107 ms |
4952 KB |
Correct. |
3 |
Correct |
119 ms |
4956 KB |
Correct. |
4 |
Correct |
147 ms |
16748 KB |
Correct. |
5 |
Correct |
76 ms |
4784 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
122 ms |
4972 KB |
Correct. |
2 |
Correct |
91 ms |
5972 KB |
Correct. |
3 |
Correct |
33 ms |
13396 KB |
Correct. |
4 |
Correct |
97 ms |
13204 KB |
Correct. |
5 |
Correct |
92 ms |
5988 KB |
Correct. |
6 |
Correct |
107 ms |
6036 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
187 ms |
4944 KB |
Correct. |
2 |
Correct |
28 ms |
5212 KB |
Correct. |
3 |
Correct |
1322 ms |
129740 KB |
Correct. |
4 |
Correct |
714 ms |
34744 KB |
Correct. |
5 |
Correct |
745 ms |
56972 KB |
Correct. |
6 |
Correct |
291 ms |
24020 KB |
Correct. |
7 |
Correct |
674 ms |
38696 KB |
Correct. |
8 |
Correct |
522 ms |
9460 KB |
Correct. |
9 |
Correct |
157 ms |
6020 KB |
Correct. |
10 |
Correct |
139 ms |
5816 KB |
Correct. |
11 |
Correct |
492 ms |
7016 KB |
Correct. |
12 |
Correct |
173 ms |
6064 KB |
Correct. |
13 |
Correct |
174 ms |
6080 KB |
Correct. |
14 |
Correct |
576 ms |
66644 KB |
Correct. |
15 |
Correct |
572 ms |
21804 KB |
Correct. |
16 |
Correct |
155 ms |
5928 KB |
Correct. |
17 |
Correct |
200 ms |
6144 KB |
Correct. |
18 |
Correct |
173 ms |
5968 KB |
Correct. |
19 |
Correct |
462 ms |
7080 KB |
Correct. |
20 |
Correct |
11 ms |
4700 KB |
Correct. |
21 |
Correct |
13 ms |
4848 KB |
Correct. |
22 |
Correct |
27 ms |
5724 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
398 ms |
5064 KB |
Correct. |
2 |
Correct |
59 ms |
5208 KB |
Correct. |
3 |
Execution timed out |
3031 ms |
136616 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |