oj.uz

답안 #974216

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974216 2024-05-03T06:28:41 Z Pannda 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 527076 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, 80);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 600 KB Correct.
2 Correct 18 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 860 KB Correct.
2 Correct 26 ms 848 KB Correct.
3 Correct 25 ms 820 KB Correct.
4 Correct 27 ms 604 KB Correct.
5 Correct 26 ms 860 KB Correct.
6 Correct 24 ms 4000 KB Correct.
7 Correct 29 ms 3860 KB Correct.
8 Correct 16 ms 7720 KB Correct.
9 Correct 26 ms 544 KB Correct.
10 Correct 27 ms 524 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 1220 KB Correct.
2 Correct 33 ms 792 KB Correct.
3 Correct 28 ms 860 KB Correct.
4 Correct 30 ms 772 KB Correct.
5 Correct 27 ms 548 KB Correct.
6 Correct 6 ms 3420 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 21340 KB Correct.
2 Correct 119 ms 820 KB Correct.
3 Correct 124 ms 824 KB Correct.
4 Correct 120 ms 800 KB Correct.
5 Correct 145 ms 348 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 828 KB Correct.
2 Correct 25 ms 604 KB Correct.
3 Correct 24 ms 604 KB Correct.
4 Correct 23 ms 3676 KB Correct.
5 Correct 22 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 860 KB Correct.
2 Correct 22 ms 780 KB Correct.
3 Correct 45 ms 28036 KB Correct.
4 Correct 16 ms 2652 KB Correct.
5 Correct 25 ms 348 KB Correct.
6 Correct 25 ms 776 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 604 KB Correct.
2 Correct 26 ms 856 KB Correct.
3 Correct 620 ms 26332 KB Correct.
4 Correct 254 ms 6948 KB Correct.
5 Correct 514 ms 16084 KB Correct.
6 Correct 213 ms 7892 KB Correct.
7 Correct 288 ms 6972 KB Correct.
8 Correct 213 ms 1640 KB Correct.
9 Correct 118 ms 828 KB Correct.
10 Correct 113 ms 1024 KB Correct.
11 Correct 206 ms 856 KB Correct.
12 Correct 133 ms 856 KB Correct.
13 Correct 130 ms 776 KB Correct.
14 Correct 233 ms 8556 KB Correct.
15 Correct 235 ms 2672 KB Correct.
16 Correct 127 ms 776 KB Correct.
17 Correct 141 ms 824 KB Correct.
18 Correct 124 ms 808 KB Correct.
19 Correct 315 ms 604 KB Correct.
20 Correct 11 ms 348 KB Correct.
21 Correct 9 ms 728 KB Correct.
22 Correct 17 ms 1372 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3032 ms 527076 KB Time limit exceeded
2 Halted 0 ms 0 KB -