oj.uz

Submission #974215

# Submission time Handle Problem Language Result Execution time Memory
974215 2024-05-03T06:27:40 Z Pannda Cyberland (APIO23_cyberland) C++17
97 / 100
 626 ms 38872 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 20 ms 856 KB Correct.
2 Correct 20 ms 828 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 844 KB Correct.
2 Correct 27 ms 772 KB Correct.
3 Correct 26 ms 824 KB Correct.
4 Correct 27 ms 856 KB Correct.
5 Correct 27 ms 812 KB Correct.
6 Correct 26 ms 4000 KB Correct.
7 Correct 31 ms 3932 KB Correct.
8 Correct 14 ms 7516 KB Correct.
9 Correct 26 ms 348 KB Correct.
10 Correct 26 ms 552 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 604 KB Correct.
2 Correct 27 ms 604 KB Correct.
3 Correct 26 ms 872 KB Correct.
4 Correct 32 ms 348 KB Correct.
5 Correct 29 ms 560 KB Correct.
6 Correct 6 ms 3380 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 21412 KB Correct.
2 Correct 119 ms 820 KB Correct.
3 Correct 111 ms 932 KB Correct.
4 Correct 115 ms 776 KB Correct.
5 Correct 142 ms 344 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1572 KB Correct.
2 Correct 26 ms 1720 KB Correct.
3 Correct 27 ms 1616 KB Correct.
4 Correct 24 ms 4440 KB Correct.
5 Correct 23 ms 1372 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1628 KB Correct.
2 Correct 23 ms 1700 KB Correct.
3 Correct 46 ms 29776 KB Correct.
4 Correct 16 ms 3164 KB Correct.
5 Correct 25 ms 1368 KB Correct.
6 Correct 28 ms 1748 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 1672 KB Correct.
2 Correct 25 ms 1116 KB Correct.
3 Correct 626 ms 28740 KB Correct.
4 Correct 252 ms 9160 KB Correct.
5 Correct 499 ms 18152 KB Correct.
6 Correct 206 ms 9436 KB Correct.
7 Correct 263 ms 8240 KB Correct.
8 Correct 216 ms 3080 KB Correct.
9 Correct 119 ms 1616 KB Correct.
10 Correct 119 ms 1780 KB Correct.
11 Correct 228 ms 2612 KB Correct.
12 Correct 133 ms 1804 KB Correct.
13 Correct 133 ms 2208 KB Correct.
14 Correct 240 ms 10264 KB Correct.
15 Correct 229 ms 4696 KB Correct.
16 Correct 134 ms 2004 KB Correct.
17 Correct 146 ms 1848 KB Correct.
18 Correct 124 ms 1828 KB Correct.
19 Correct 324 ms 2620 KB Correct.
20 Correct 10 ms 600 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 Correct 139 ms 1588 KB Correct.
2 Correct 28 ms 1112 KB Correct.
3 Incorrect 353 ms 38872 KB Wrong Answer.
4 Halted 0 ms 0 KB -