oj.uz

Submission #749136

# Submission time Handle Problem Language Result Execution time Memory
749136 2023-05-27T11:46:36 Z Alan Cyberland (APIO23_cyberland) C++17
100 / 100
 2580 ms 146704 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
 
struct edge {
    int v;
    ld w;
    int k;
    bool operator< (edge b) const {
        if (k != b.k) return k > b.k;
        return w > b.w;
    }
};
vector<edge> g[100005];
bool vis[100005];
ld di[100005][81];
const ld inf = 1e18;
int h;
 
void dfs (int u) {
    vis[u] = true;
    if (u == h) return;
    for (auto& [v, w, k] : g[u]) if (!vis[v]) dfs(v);
}
 
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) {
    h = H;
    K = min(K, 80);
    for (int i = 0; i < N; i++) {
        g[i].clear();
        vis[i] = false;
        for (int j = 0; j <= K; j++) di[i][j] = inf;
    }
    for (int i = 0; i < M; i++) {
        g[x[i]].push_back({y[i], ld(c[i]), 0});
        g[y[i]].push_back({x[i], ld(c[i]), 0});
    }
    dfs(0);
    if (!vis[H]) return -1;
    priority_queue<edge, vector<edge>> pq;
    for (int i = 1; i < N; i++) if (arr[i] == 0 && vis[i]) {
        pq.push({i, 0, 0});
        di[i][0] = 0;
    }
    pq.push({0, 0, 0});
    di[0][0] = 0;
    while (!pq.empty()) {
        auto [u, w, k] = pq.top();
        pq.pop();
        if (u == H) continue;
        if (di[u][k] != w) continue;
        for (auto& [v, vw, vk] : g[u]) if (arr[v] != 0) {
            if (arr[v] == 2 && k+1 <= K && di[v][k+1] > (w+vw)/2) {
                di[v][k+1] = (w+vw)/2;
                pq.push({v, (w+vw)/2, k+1});
            }
            if (di[v][k] > w+vw) {
                di[v][k] = w+vw;
                pq.push({v, w+vw, k});
            }
        }
    }
    ld ans = inf;
    for (int i = 0; i <= K; i++) ans = min(ans, di[H][i]);
    return ans == inf ? -1 : ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2772 KB Correct.
2 Correct 27 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4280 KB Correct.
2 Correct 40 ms 4256 KB Correct.
3 Correct 36 ms 4308 KB Correct.
4 Correct 38 ms 4292 KB Correct.
5 Correct 41 ms 4308 KB Correct.
6 Correct 40 ms 16988 KB Correct.
7 Correct 51 ms 16708 KB Correct.
8 Correct 30 ms 30688 KB Correct.
9 Correct 37 ms 2876 KB Correct.
10 Correct 35 ms 2900 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4232 KB Correct.
2 Correct 39 ms 4308 KB Correct.
3 Correct 36 ms 4336 KB Correct.
4 Correct 36 ms 2860 KB Correct.
5 Correct 36 ms 2772 KB Correct.
6 Correct 14 ms 14360 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 86052 KB Correct.
2 Correct 107 ms 4132 KB Correct.
3 Correct 93 ms 4100 KB Correct.
4 Correct 97 ms 4132 KB Correct.
5 Correct 72 ms 2836 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4456 KB Correct.
2 Correct 35 ms 4500 KB Correct.
3 Correct 37 ms 4496 KB Correct.
4 Correct 41 ms 18500 KB Correct.
5 Correct 31 ms 2996 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4564 KB Correct.
2 Correct 30 ms 4600 KB Correct.
3 Correct 100 ms 111020 KB Correct.
4 Correct 32 ms 14020 KB Correct.
5 Correct 34 ms 2884 KB Correct.
6 Correct 33 ms 4652 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 4508 KB Correct.
2 Correct 21 ms 5524 KB Correct.
3 Correct 907 ms 138700 KB Correct.
4 Correct 499 ms 34596 KB Correct.
5 Correct 619 ms 64912 KB Correct.
6 Correct 275 ms 30636 KB Correct.
7 Correct 441 ms 37176 KB Correct.
8 Correct 281 ms 7944 KB Correct.
9 Correct 97 ms 4616 KB Correct.
10 Correct 91 ms 4632 KB Correct.
11 Correct 257 ms 4676 KB Correct.
12 Correct 114 ms 4556 KB Correct.
13 Correct 111 ms 4612 KB Correct.
14 Correct 442 ms 69916 KB Correct.
15 Correct 341 ms 21108 KB Correct.
16 Correct 102 ms 4508 KB Correct.
17 Correct 116 ms 4532 KB Correct.
18 Correct 107 ms 4536 KB Correct.
19 Correct 245 ms 4428 KB Correct.
20 Correct 8 ms 2772 KB Correct.
21 Correct 9 ms 4136 KB Correct.
22 Correct 21 ms 5588 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 4600 KB Correct.
2 Correct 44 ms 5572 KB Correct.
3 Correct 1301 ms 146704 KB Correct.
4 Correct 421 ms 12340 KB Correct.
5 Correct 1472 ms 64904 KB Correct.
6 Correct 617 ms 30656 KB Correct.
7 Correct 982 ms 56040 KB Correct.
8 Correct 423 ms 4940 KB Correct.
9 Correct 209 ms 4564 KB Correct.
10 Correct 200 ms 4644 KB Correct.
11 Correct 296 ms 2876 KB Correct.
12 Correct 231 ms 4604 KB Correct.
13 Correct 239 ms 4528 KB Correct.
14 Correct 2580 ms 65080 KB Correct.
15 Correct 2001 ms 73804 KB Correct.
16 Correct 828 ms 29516 KB Correct.
17 Correct 447 ms 8084 KB Correct.
18 Correct 224 ms 4628 KB Correct.
19 Correct 273 ms 4596 KB Correct.
20 Correct 243 ms 4556 KB Correct.
21 Correct 626 ms 4588 KB Correct.
22 Correct 17 ms 2772 KB Correct.
23 Correct 20 ms 4132 KB Correct.
24 Correct 46 ms 5588 KB Correct.