#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
const int MAXN = 100005;
struct disj {
int pa[MAXN];
void init(int n) { iota(pa, pa + n + 1, 0); }
int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }
bool uni(int p, int q) {
p = find(p);
q = find(q);
if (p == q)
return 0;
pa[q] = p;
return 1;
}
} disj;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
K = min(K, 69); // Limiting K to a reasonable value to handle large inputs
vector<vector<pi>> gph(N);
disj.init(N);
for (int i = 0; i < M; i++) {
if (x[i] != H && y[i] != H)
disj.uni(x[i], y[i]);
gph[x[i]].push_back({c[i], y[i]});
gph[y[i]].push_back({c[i], x[i]});
}
vector<double> pwr(K + 1, 1);
for (int i = 1; i <= K; i++)
pwr[i] = pwr[i - 1] / 2;
arr[0] = 0; // Ensuring starting point has no special ability
vector<vector<double>> dist(K + 1, vector<double>(N, 1e18));
using node = tuple<double, int, int>;
priority_queue<node, vector<node>, greater<node>> pq;
auto enq = [&](int k, int x, double d) {
if (dist[k][x] > d) {
dist[k][x] = d;
pq.push({d, k, x});
}
};
enq(K, 0, 0); // Start from country 0 with full divide-by-2 abilities
while (!pq.empty()) {
auto [d, k, v] = pq.top();
pq.pop();
if (dist[k][v] < d)
continue;
if (v == H)
return d; // Return the distance once Cyberland is reached
for (auto &[cost, w] : gph[v]) {
enq(k, w, d + cost);
if (arr[w] == 2 && k > 0) {
enq(k - 1, w, d + cost * pwr[K - k + 1]);
} else if (arr[w] == 0) {
enq(k, w, 0); // If the country's ability sets time to 0
}
}
}
return -1; // If Cyberland is not reachable
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
25 ms |
856 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
1708 KB |
Correct. |
2 |
Correct |
25 ms |
1820 KB |
Correct. |
3 |
Correct |
24 ms |
1852 KB |
Correct. |
4 |
Correct |
25 ms |
1816 KB |
Correct. |
5 |
Correct |
24 ms |
1792 KB |
Correct. |
6 |
Correct |
20 ms |
4684 KB |
Correct. |
7 |
Correct |
28 ms |
4392 KB |
Correct. |
8 |
Correct |
14 ms |
7772 KB |
Correct. |
9 |
Correct |
30 ms |
1368 KB |
Correct. |
10 |
Correct |
23 ms |
1372 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
27 ms |
1760 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
73 ms |
20572 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
1664 KB |
Correct. |
2 |
Correct |
24 ms |
1860 KB |
Correct. |
3 |
Correct |
30 ms |
1868 KB |
Correct. |
4 |
Correct |
22 ms |
4132 KB |
Correct. |
5 |
Correct |
21 ms |
1368 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
24 ms |
1816 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
173 ms |
2392 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
382 ms |
3468 KB |
Wrong Answer. |
2 |
Halted |
0 ms |
0 KB |
- |