oj.uz

Submission #974223

# Submission time Handle Problem Language Result Execution time Memory
974223 2024-05-03T06:30:03 Z Pannda Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 527684 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, 40);
    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 600 KB Correct.
2 Correct 18 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 856 KB Correct.
2 Correct 26 ms 848 KB Correct.
3 Correct 25 ms 860 KB Correct.
4 Correct 25 ms 828 KB Correct.
5 Correct 26 ms 860 KB Correct.
6 Correct 22 ms 4000 KB Correct.
7 Correct 30 ms 3932 KB Correct.
8 Correct 16 ms 7516 KB Correct.
9 Correct 25 ms 564 KB Correct.
10 Correct 24 ms 344 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 856 KB Correct.
2 Correct 27 ms 604 KB Correct.
3 Correct 25 ms 852 KB Correct.
4 Correct 28 ms 348 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 223 ms 21412 KB Correct.
2 Correct 120 ms 824 KB Correct.
3 Correct 109 ms 828 KB Correct.
4 Correct 117 ms 824 KB Correct.
5 Correct 139 ms 348 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 828 KB Correct.
2 Correct 25 ms 600 KB Correct.
3 Correct 24 ms 604 KB Correct.
4 Correct 23 ms 3852 KB Correct.
5 Correct 23 ms 560 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 848 KB Correct.
2 Correct 22 ms 816 KB Correct.
3 Correct 48 ms 27988 KB Correct.
4 Correct 16 ms 2648 KB Correct.
5 Correct 25 ms 344 KB Correct.
6 Correct 26 ms 900 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 824 KB Correct.
2 Correct 24 ms 860 KB Correct.
3 Correct 600 ms 26452 KB Correct.
4 Correct 244 ms 6848 KB Correct.
5 Correct 492 ms 16076 KB Correct.
6 Correct 213 ms 7900 KB Correct.
7 Correct 251 ms 6684 KB Correct.
8 Correct 217 ms 1464 KB Correct.
9 Correct 119 ms 840 KB Correct.
10 Correct 110 ms 800 KB Correct.
11 Correct 207 ms 844 KB Correct.
12 Correct 134 ms 772 KB Correct.
13 Correct 128 ms 824 KB Correct.
14 Correct 236 ms 8564 KB Correct.
15 Correct 235 ms 2652 KB Correct.
16 Correct 126 ms 772 KB Correct.
17 Correct 143 ms 816 KB Correct.
18 Correct 124 ms 788 KB Correct.
19 Correct 313 ms 600 KB Correct.
20 Correct 10 ms 344 KB Correct.
21 Correct 10 ms 604 KB Correct.
22 Correct 17 ms 1372 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3062 ms 527684 KB Time limit exceeded
2 Halted 0 ms 0 KB -