#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int x , vector<bool>&reach , vector<vector<pair<int ,int>>> &adj , int H)
{
if(x == H || reach[x])
return ;
reach[x] = 1;
for(auto [u , cost] : adj[x])
{
dfs(u , reach , adj , H);
}
}
using Node = tuple<double , int , int>;
priority_queue<Node , vector<Node> , greater<Node>> pq;
void upd(int x , int k , double d , vector<vector<double>> &dist)
{
if(dist[x][k] > d)
{
dist[x][k] = d;
pq.push({d , x , k});
}
}
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)
{
pq = priority_queue<Node , vector<Node> , greater<Node>> ();
K = min(K , 70);
vector<vector<pair<int , int>>> adj(N);
vector<bool> reach(N);
vector<double> pwr(K + 1);
pwr[0] = 1;
for(int i = 1 ; i <= K ; i++)
{
pwr[i] = pwr[i - 1]/2.0;
}
for(int i = 0 ; i < M ; i++)
{
adj[x[i]].push_back({y[i] , c[i]});
adj[y[i]].push_back({x[i] , c[i]});
}
vector<vector<double>> dist(N , vector<double>(K + 1 , 1e18));
arr[0] = 0;
upd(H , 0 , 0 , dist);
dfs(0 , reach ,adj ,H);
while(!pq.empty())
{
auto [d , x , k] = pq.top();
pq.pop();
if(arr[x] == 0)
{
return d;
}
for(auto [u , cost] : adj[x])
{
if(!reach[u])
continue;
upd(u , k , cost*pwr[k] + d , dist);
if(arr[x] == 2 && k < K)
{
int p = k + 1;
upd(u , p , cost*pwr[p] + d , dist);
}
}
}
return -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
856 KB |
Correct. |
2 |
Correct |
13 ms |
752 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
1624 KB |
Correct. |
2 |
Correct |
23 ms |
1884 KB |
Correct. |
3 |
Correct |
17 ms |
1628 KB |
Correct. |
4 |
Correct |
18 ms |
1884 KB |
Correct. |
5 |
Correct |
18 ms |
1884 KB |
Correct. |
6 |
Correct |
15 ms |
4752 KB |
Correct. |
7 |
Correct |
20 ms |
4700 KB |
Correct. |
8 |
Correct |
10 ms |
7948 KB |
Correct. |
9 |
Correct |
18 ms |
1372 KB |
Correct. |
10 |
Correct |
17 ms |
1372 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
1824 KB |
Correct. |
2 |
Correct |
18 ms |
1804 KB |
Correct. |
3 |
Correct |
16 ms |
1720 KB |
Correct. |
4 |
Correct |
17 ms |
1372 KB |
Correct. |
5 |
Correct |
17 ms |
1372 KB |
Correct. |
6 |
Correct |
4 ms |
3420 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
23388 KB |
Correct. |
2 |
Correct |
16 ms |
1752 KB |
Correct. |
3 |
Correct |
17 ms |
1660 KB |
Correct. |
4 |
Correct |
16 ms |
1748 KB |
Correct. |
5 |
Correct |
18 ms |
1372 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
1672 KB |
Correct. |
2 |
Correct |
19 ms |
1884 KB |
Correct. |
3 |
Correct |
19 ms |
1808 KB |
Correct. |
4 |
Correct |
19 ms |
4700 KB |
Correct. |
5 |
Correct |
17 ms |
1372 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
1724 KB |
Correct. |
2 |
Correct |
17 ms |
1624 KB |
Correct. |
3 |
Correct |
37 ms |
29876 KB |
Correct. |
4 |
Correct |
13 ms |
3316 KB |
Correct. |
5 |
Correct |
18 ms |
1372 KB |
Correct. |
6 |
Correct |
18 ms |
1736 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
1764 KB |
Correct. |
2 |
Correct |
3 ms |
1116 KB |
Correct. |
3 |
Correct |
56 ms |
28908 KB |
Correct. |
4 |
Correct |
36 ms |
9156 KB |
Correct. |
5 |
Correct |
36 ms |
18260 KB |
Correct. |
6 |
Correct |
21 ms |
9308 KB |
Correct. |
7 |
Correct |
35 ms |
7988 KB |
Correct. |
8 |
Correct |
37 ms |
3076 KB |
Correct. |
9 |
Correct |
17 ms |
1732 KB |
Correct. |
10 |
Correct |
18 ms |
1652 KB |
Correct. |
11 |
Correct |
36 ms |
2636 KB |
Correct. |
12 |
Correct |
18 ms |
1720 KB |
Correct. |
13 |
Correct |
34 ms |
1816 KB |
Correct. |
14 |
Correct |
36 ms |
10412 KB |
Correct. |
15 |
Correct |
35 ms |
4576 KB |
Correct. |
16 |
Correct |
17 ms |
1828 KB |
Correct. |
17 |
Correct |
19 ms |
1844 KB |
Correct. |
18 |
Correct |
20 ms |
1856 KB |
Correct. |
19 |
Correct |
34 ms |
2744 KB |
Correct. |
20 |
Correct |
2 ms |
604 KB |
Correct. |
21 |
Correct |
2 ms |
768 KB |
Correct. |
22 |
Correct |
2 ms |
1116 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
2028 KB |
Correct. |
2 |
Correct |
3 ms |
1628 KB |
Correct. |
3 |
Correct |
87 ms |
74848 KB |
Correct. |
4 |
Correct |
42 ms |
4688 KB |
Correct. |
5 |
Correct |
36 ms |
29520 KB |
Correct. |
6 |
Correct |
22 ms |
12372 KB |
Correct. |
7 |
Correct |
38 ms |
14592 KB |
Correct. |
8 |
Correct |
38 ms |
3116 KB |
Correct. |
9 |
Correct |
20 ms |
2092 KB |
Correct. |
10 |
Correct |
36 ms |
2044 KB |
Correct. |
11 |
Correct |
129 ms |
1596 KB |
Correct. |
12 |
Correct |
22 ms |
2152 KB |
Correct. |
13 |
Correct |
20 ms |
2144 KB |
Correct. |
14 |
Correct |
69 ms |
29780 KB |
Correct. |
15 |
Correct |
49 ms |
35908 KB |
Correct. |
16 |
Correct |
42 ms |
13300 KB |
Correct. |
17 |
Correct |
36 ms |
4416 KB |
Correct. |
18 |
Correct |
19 ms |
2108 KB |
Correct. |
19 |
Correct |
21 ms |
2260 KB |
Correct. |
20 |
Correct |
22 ms |
2080 KB |
Correct. |
21 |
Correct |
37 ms |
2920 KB |
Correct. |
22 |
Correct |
2 ms |
604 KB |
Correct. |
23 |
Correct |
2 ms |
968 KB |
Correct. |
24 |
Correct |
3 ms |
1372 KB |
Correct. |