oj.uz

Submission #974220

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1624 KB Correct.
2 Correct 26 ms 1476 KB Correct.
3 Correct 28 ms 1580 KB Correct.
4 Correct 26 ms 1372 KB Correct.
5 Correct 27 ms 1628 KB Correct.
6 Correct 23 ms 4768 KB Correct.
7 Correct 29 ms 4700 KB Correct.
8 Correct 14 ms 8028 KB Correct.
9 Correct 25 ms 1304 KB Correct.
10 Correct 25 ms 1116 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1628 KB Correct.
2 Correct 27 ms 1624 KB Correct.
3 Correct 25 ms 1632 KB Correct.
4 Correct 27 ms 1112 KB Correct.
5 Correct 27 ms 1312 KB Correct.
6 Correct 6 ms 3420 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 22436 KB Correct.
2 Correct 118 ms 1360 KB Correct.
3 Correct 112 ms 1512 KB Correct.
4 Correct 114 ms 1576 KB Correct.
5 Correct 145 ms 1544 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1356 KB Correct.
2 Correct 27 ms 1372 KB Correct.
3 Correct 25 ms 1428 KB Correct.
4 Correct 23 ms 4400 KB Correct.
5 Correct 22 ms 1116 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1624 KB Correct.
2 Correct 22 ms 1528 KB Correct.
3 Correct 55 ms 29268 KB Correct.
4 Correct 16 ms 3160 KB Correct.
5 Correct 25 ms 1116 KB Correct.
6 Correct 25 ms 1540 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 1564 KB Correct.
2 Correct 24 ms 1112 KB Correct.
3 Correct 556 ms 27732 KB Correct.
4 Correct 249 ms 8048 KB Correct.
5 Correct 469 ms 17108 KB Correct.
6 Correct 207 ms 8924 KB Correct.
7 Correct 273 ms 7204 KB Correct.
8 Correct 220 ms 2988 KB Correct.
9 Correct 127 ms 1576 KB Correct.
10 Correct 116 ms 1540 KB Correct.
11 Correct 212 ms 2120 KB Correct.
12 Correct 141 ms 1808 KB Correct.
13 Correct 131 ms 1544 KB Correct.
14 Correct 259 ms 10060 KB Correct.
15 Correct 227 ms 3924 KB Correct.
16 Correct 125 ms 1584 KB Correct.
17 Correct 149 ms 1604 KB Correct.
18 Correct 124 ms 1824 KB Correct.
19 Correct 321 ms 2208 KB Correct.
20 Correct 10 ms 600 KB Correct.
21 Correct 10 ms 804 KB Correct.
22 Correct 17 ms 1368 KB Correct.

Subtask #8
0.0 / 3.0

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