oj.uz

Submission #974224

# Submission time Handle Problem Language Result Execution time Memory
974224 2024-05-03T06:30:35 Z Pannda Cyberland (APIO23_cyberland) C++17
97 / 100
 656 ms 37836 KB 
#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;

double solve(int n, int m, int k, int t, vector<int> U, vector<int> V, vector<int> W, vector<int> type) {
    k = min(k, 30);
    vector<vector<array<int, 2>>> adj(n);
    for (int i = 0; i < m; i++) {
        auto [u, v, w] = array<int, 3>{U[i], V[i], W[i]};
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    constexpr double INF = 1e18;
    constexpr double EPS = 1e-9;
    auto equal = [](double x, double y) -> bool {
        return abs(x - y) < EPS;
    };

    vector<vector<double>> dist(n, vector<double>(k + 1, INF));
    dist[t][0] = 0;
    priority_queue<pair<double, pair<int, int>>, vector<pair<double, pair<int, int>>>, greater<>> pq;
    pq.push(make_pair(dist[t][0], make_pair(0, t)));
    while (!pq.empty()) {
        auto [d, cu] = pq.top();
        auto [c, u] = cu;
        pq.pop();
        if (!equal(dist[u][c], d)) continue;
        for (auto [v, ww] : adj[u]) {
            if (v == t) continue;
            double w = ww;
            w /= (1 << c);
            if (d + w + EPS < dist[v][c]) {
                dist[v][c] = d + w;
                pq.push(make_pair(dist[v][c], make_pair(c, v)));
            }
            if (type[v] == 2 && c + 1 <= k) {
                c++;
                if (d + w + EPS < dist[v][c]) {
                    dist[v][c] = d + w;
                    pq.push(make_pair(dist[v][c], make_pair(c, v)));
                }
                c--;
            }
        }
    }

    type[0] = 0;
    vector<bool> reachable(n, false);
    queue<int> que;
    reachable[0] = true;
    que.push(0);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto [v, w] : adj[u]) {
            if (v == t) continue;
            if (!reachable[v]) {
                reachable[v] = true;
                que.push(v);
            }
        }
    }

    double ans = INF;
    for (int u = 0; u < n; u++) {
        if (reachable[u] && type[u] == 0) {
            double val = *min_element(dist[u].begin(), dist[u].end());
            ans = min(ans, val);
        }
    }

    if (equal(ans, INF)) {
        return -1;
    } else {
        return ans;
    }

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 604 KB Correct.
2 Correct 18 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 860 KB Correct.
2 Correct 26 ms 860 KB Correct.
3 Correct 24 ms 860 KB Correct.
4 Correct 26 ms 604 KB Correct.
5 Correct 28 ms 816 KB Correct.
6 Correct 22 ms 4000 KB Correct.
7 Correct 29 ms 3928 KB Correct.
8 Correct 14 ms 7516 KB Correct.
9 Correct 26 ms 344 KB Correct.
10 Correct 28 ms 860 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 604 KB Correct.
2 Correct 26 ms 604 KB Correct.
3 Correct 25 ms 860 KB Correct.
4 Correct 29 ms 568 KB Correct.
5 Correct 27 ms 348 KB Correct.
6 Correct 6 ms 3420 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 21412 KB Correct.
2 Correct 135 ms 604 KB Correct.
3 Correct 110 ms 828 KB Correct.
4 Correct 114 ms 780 KB Correct.
5 Correct 142 ms 536 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 820 KB Correct.
2 Correct 36 ms 604 KB Correct.
3 Correct 34 ms 812 KB Correct.
4 Correct 23 ms 3676 KB Correct.
5 Correct 22 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 856 KB Correct.
2 Correct 22 ms 800 KB Correct.
3 Correct 44 ms 28012 KB Correct.
4 Correct 16 ms 2648 KB Correct.
5 Correct 27 ms 556 KB Correct.
6 Correct 31 ms 776 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 796 KB Correct.
2 Correct 25 ms 860 KB Correct.
3 Correct 656 ms 26212 KB Correct.
4 Correct 288 ms 6876 KB Correct.
5 Correct 571 ms 16104 KB Correct.
6 Correct 221 ms 8128 KB Correct.
7 Correct 275 ms 6904 KB Correct.
8 Correct 221 ms 1800 KB Correct.
9 Correct 122 ms 844 KB Correct.
10 Correct 113 ms 808 KB Correct.
11 Correct 220 ms 856 KB Correct.
12 Correct 143 ms 784 KB Correct.
13 Correct 129 ms 792 KB Correct.
14 Correct 232 ms 8776 KB Correct.
15 Correct 236 ms 2640 KB Correct.
16 Correct 124 ms 772 KB Correct.
17 Correct 147 ms 828 KB Correct.
18 Correct 124 ms 804 KB Correct.
19 Correct 314 ms 600 KB Correct.
20 Correct 11 ms 344 KB Correct.
21 Correct 10 ms 600 KB Correct.
22 Correct 17 ms 1372 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 1400 KB Correct.
2 Correct 25 ms 1416 KB Correct.
3 Incorrect 372 ms 37836 KB Wrong Answer.
4 Halted 0 ms 0 KB -