#include "cyberland.h"
// #include "stub.cpp"
#include <bits/stdc++.h>
#include <vector>
#pragma GCC optimize("Ofast")
#define lg long long
#define ld long double
#define ff first
#define sf second.first
#define ss second.second
using namespace std;
const lg N = 1e5+5, K = 71;
ld dist[N][K];
lg in_queue[N][K];
vector<array<lg, 2>> adj[N];
double solve(int n, int m, int k, int h, std::vector<int> g, std::vector<int> r, std::vector<int> d, std::vector<int> t)
{
k = min(k, 70);
for(int i = 0; i < n; i++) adj[i].clear();
for(int i = 0; i < m; i++)
{
adj[g[i]].push_back({r[i], d[i]});
adj[r[i]].push_back({g[i], d[i]});
}
adj[h].clear();
for(int i = 0; i < n; i++)
{
for(int j = 0; j <= k; j++)
{
dist[i][j] = 1e18;
in_queue[i][j] = 0;
}
}
dist[0][k] = 0;
priority_queue<pair<ld, pair<lg, lg>>> pq;
pq.push({-dist[0][k], {0, k}});
in_queue[0][k] = 1;
while(pq.size())
{
pair<ld, pair<lg, lg>> p = pq.top();
pq.pop();
in_queue[p.sf][p.ss] = 0;
for(auto [it, c] : adj[p.sf])
{
ld cost = dist[p.sf][p.ss]+c;
if(t[it] == 0) cost = 0;
if(t[it] == 2 && p.ss > 0 && dist[it][p.ss-1] > (cost)/2.0)
{
dist[it][p.ss-1] = cost/2.0;
if(!in_queue[it][p.ss-1])pq.push({-dist[it][p.ss-1], {it, p.ss-1}});
in_queue[it][p.ss-1] = true;
}
if(dist[it][p.ss] > cost)
{
dist[it][p.ss] = cost;
if(!in_queue[it][p.ss])pq.push({-dist[it][p.ss], {it, p.ss}});
in_queue[it][p.ss] = true;
}
}
}
ld ans = 1e18;
for(int i = 0; i <= k; i++)
{
ans = min(ans, dist[h][i]);
}
if(ans > 1e15)
{
ans = -1;
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
2772 KB |
Correct. |
2 |
Correct |
31 ms |
2804 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
4564 KB |
Correct. |
2 |
Correct |
38 ms |
4448 KB |
Correct. |
3 |
Correct |
35 ms |
4480 KB |
Correct. |
4 |
Correct |
37 ms |
4464 KB |
Correct. |
5 |
Correct |
38 ms |
4464 KB |
Correct. |
6 |
Correct |
43 ms |
19940 KB |
Correct. |
7 |
Correct |
54 ms |
19600 KB |
Correct. |
8 |
Correct |
37 ms |
37064 KB |
Correct. |
9 |
Correct |
35 ms |
2892 KB |
Correct. |
10 |
Correct |
35 ms |
2912 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
4436 KB |
Correct. |
2 |
Correct |
37 ms |
4436 KB |
Correct. |
3 |
Correct |
37 ms |
4420 KB |
Correct. |
4 |
Correct |
35 ms |
2888 KB |
Correct. |
5 |
Correct |
35 ms |
2892 KB |
Correct. |
6 |
Correct |
17 ms |
16724 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
535 ms |
104468 KB |
Correct. |
2 |
Correct |
641 ms |
4528 KB |
Correct. |
3 |
Correct |
547 ms |
4492 KB |
Correct. |
4 |
Correct |
567 ms |
4456 KB |
Correct. |
5 |
Correct |
355 ms |
3000 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
4564 KB |
Correct. |
2 |
Correct |
33 ms |
4608 KB |
Correct. |
3 |
Correct |
34 ms |
4524 KB |
Correct. |
4 |
Correct |
42 ms |
20048 KB |
Correct. |
5 |
Correct |
30 ms |
2888 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
4564 KB |
Correct. |
2 |
Correct |
30 ms |
4540 KB |
Correct. |
3 |
Correct |
102 ms |
135220 KB |
Correct. |
4 |
Correct |
33 ms |
15068 KB |
Correct. |
5 |
Correct |
32 ms |
2788 KB |
Correct. |
6 |
Correct |
32 ms |
4564 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
306 ms |
5064 KB |
Correct. |
2 |
Correct |
36 ms |
6476 KB |
Correct. |
3 |
Correct |
2198 ms |
170160 KB |
Correct. |
4 |
Correct |
1539 ms |
40856 KB |
Correct. |
5 |
Correct |
831 ms |
84684 KB |
Correct. |
6 |
Correct |
365 ms |
33756 KB |
Correct. |
7 |
Correct |
1420 ms |
44544 KB |
Correct. |
8 |
Correct |
1201 ms |
9072 KB |
Correct. |
9 |
Correct |
250 ms |
5156 KB |
Correct. |
10 |
Correct |
263 ms |
5076 KB |
Correct. |
11 |
Correct |
1111 ms |
5040 KB |
Correct. |
12 |
Correct |
289 ms |
5044 KB |
Correct. |
13 |
Correct |
267 ms |
5096 KB |
Correct. |
14 |
Correct |
1451 ms |
84620 KB |
Correct. |
15 |
Correct |
1494 ms |
24952 KB |
Correct. |
16 |
Correct |
263 ms |
4984 KB |
Correct. |
17 |
Correct |
339 ms |
5120 KB |
Correct. |
18 |
Correct |
313 ms |
5100 KB |
Correct. |
19 |
Correct |
882 ms |
5116 KB |
Correct. |
20 |
Correct |
24 ms |
2900 KB |
Correct. |
21 |
Correct |
25 ms |
4612 KB |
Correct. |
22 |
Correct |
26 ms |
5844 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
788 ms |
5572 KB |
Correct. |
2 |
Correct |
78 ms |
7360 KB |
Correct. |
3 |
Correct |
1389 ms |
177240 KB |
Correct. |
4 |
Execution timed out |
3071 ms |
14100 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |