oj.uz

답안 #974212

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974212 2024-05-03T06:25:17 Z Pannda 사이버랜드 (APIO23_cyberland) C++17
40 / 100
 243 ms 22584 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 < n - 1; 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-12;
    auto equal = [](double x, double y) -> bool {
        return abs(x - y) < EPS;
    };

    vector<vector<double>> dist(n, vector<double>(k + 1, INF));
    dist[t] = vector<double>(k + 1, 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, w] : adj[u]) {
            if (v == t) continue;
            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
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 1628 KB Correct.
2 Correct 26 ms 1884 KB Correct.
3 Correct 24 ms 1692 KB Correct.
4 Correct 26 ms 1884 KB Correct.
5 Correct 26 ms 1880 KB Correct.
6 Correct 23 ms 4768 KB Correct.
7 Correct 29 ms 5156 KB Correct.
8 Correct 15 ms 8028 KB Correct.
9 Correct 25 ms 1452 KB Correct.
10 Correct 25 ms 1440 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 1624 KB Correct.
2 Correct 26 ms 1628 KB Correct.
3 Correct 25 ms 1672 KB Correct.
4 Correct 27 ms 1364 KB Correct.
5 Correct 27 ms 1372 KB Correct.
6 Correct 6 ms 3616 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 22584 KB Correct.
2 Correct 125 ms 1692 KB Correct.
3 Correct 113 ms 1764 KB Correct.
4 Correct 118 ms 1672 KB Correct.
5 Correct 155 ms 1412 KB Correct.

Subtask #5
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -