#include "cyberland.h"
#include <bits/stdc++.h>
const int MAX_N = 1e5 + 10;
const int MAX_K = 31;
typedef long double ld;
ld dist[2][MAX_N][MAX_K];
std::vector<std::pair<int, int> > g[MAX_N];
bool used[MAX_N];
void dfs(int x) {
if(used[x]) { return; }
used[x] = true;
for(const auto &it : g[x]) {
dfs(it.first);
}
}
ld pw[MAX_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) {
for(int i = 0; i < N; i ++) {
g[i].resize(0);
used[i] = false;
}
for(int i = 0; i < M; i ++) {
g[x[i]].push_back({y[i], c[i]});
g[y[i]].push_back({x[i], c[i]});
}
dfs(0);
K = std::min(K, MAX_K - 1);
pw[0] = 1;
for(int i = 1; i <= K; i ++) {
pw[i] = (pw[i - 1] * 2.0);
}
for(int i = 0; i < N; i ++) {
for(int j = 0; j <= K; j ++) {
dist[0][i][j] = dist[1][i][j] = 1e18;
}
}
for(int left = K; left >= 0; left --) {
std::priority_queue<std::pair<ld, int> > pq;
for(int i = 0; i < N; i ++) {
if(i == 0) {
dist[0][i][left] = 0;
}
if(dist[0][i][left] < 1e17) {
pq.push({-dist[0][i][left], i});
}
if(dist[1][i][left] < 1e17) {
pq.push({-dist[1][i][left], i + MAX_N});
}
}
while(!pq.empty()) {
auto curr = pq.top(); pq.pop();
curr.first *= -1;
bool used = curr.second / MAX_N;
curr.second %= MAX_N;
if(curr.first > dist[used][curr.second][left]) {
continue;
}
if(curr.second == H) { continue; }
for(const auto &it : g[curr.second]) {
ld new_cost = curr.first + it.second / pw[left];
if(dist[0][it.first][left] > new_cost) {
dist[0][it.first][left] = new_cost;
pq.push({-new_cost, it.first});
}
}
}
for(int i = 0; i < N; i ++) {
if(arr[i] == 2) {
dist[1][i][left - 1] = dist[0][i][left];
} else if(arr[i] == 0) {
if(dist[0][i][left] < 1e17) {
dist[1][i][left - 1] = 0;
}
}
}
}
ld ret = std::min(dist[0][H][0], dist[1][H][0]);
if(ret > 1e17) {
return -1;
}
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
2772 KB |
Correct. |
2 |
Correct |
47 ms |
3080 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
165 ms |
3888 KB |
Correct. |
2 |
Correct |
198 ms |
3756 KB |
Correct. |
3 |
Correct |
187 ms |
3728 KB |
Correct. |
4 |
Correct |
200 ms |
3824 KB |
Correct. |
5 |
Correct |
203 ms |
3724 KB |
Correct. |
6 |
Correct |
248 ms |
12892 KB |
Correct. |
7 |
Correct |
345 ms |
12664 KB |
Correct. |
8 |
Correct |
153 ms |
23236 KB |
Correct. |
9 |
Correct |
123 ms |
2816 KB |
Correct. |
10 |
Correct |
121 ms |
2828 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
423 ms |
3916 KB |
Correct. |
2 |
Correct |
419 ms |
4932 KB |
Correct. |
3 |
Correct |
389 ms |
4740 KB |
Correct. |
4 |
Correct |
219 ms |
3704 KB |
Correct. |
5 |
Correct |
223 ms |
3700 KB |
Correct. |
6 |
Correct |
109 ms |
11724 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
297 ms |
65128 KB |
Correct. |
2 |
Correct |
261 ms |
4920 KB |
Correct. |
3 |
Correct |
242 ms |
4744 KB |
Correct. |
4 |
Correct |
246 ms |
4800 KB |
Correct. |
5 |
Correct |
143 ms |
3684 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
112 ms |
3816 KB |
Correct. |
2 |
Correct |
120 ms |
3808 KB |
Correct. |
3 |
Correct |
125 ms |
3724 KB |
Correct. |
4 |
Correct |
189 ms |
13084 KB |
Correct. |
5 |
Correct |
78 ms |
2772 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
256 ms |
3880 KB |
Correct. |
2 |
Correct |
191 ms |
5004 KB |
Correct. |
3 |
Correct |
120 ms |
83100 KB |
Correct. |
4 |
Correct |
192 ms |
11148 KB |
Correct. |
5 |
Correct |
136 ms |
3688 KB |
Correct. |
6 |
Correct |
225 ms |
4864 KB |
Correct. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
289 ms |
3872 KB |
Correct. |
2 |
Correct |
40 ms |
4728 KB |
Correct. |
3 |
Incorrect |
797 ms |
104428 KB |
Wrong Answer. |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
290 ms |
3864 KB |
Correct. |
2 |
Correct |
40 ms |
4704 KB |
Correct. |
3 |
Incorrect |
418 ms |
110792 KB |
Wrong Answer. |
4 |
Halted |
0 ms |
0 KB |
- |