oj.uz

답안 #969394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969394 2024-04-25T05:49:53 Z CDuong 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 1345 ms 2097152 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
#define i64 long long
#define ff first
#define ss second

using namespace std;

double solve(int n, int m, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    vector<vector<int>> G(n);
    for (int i = 0; i < m; ++i) {
        G[x[i]].emplace_back(i);
        G[y[i]].emplace_back(i);
    }

    // cout << n << " " << m << endl;

    vector<vector<double>> dis(n, vector<double>(K + 1, 1e18));
    priority_queue<pair<double, pair<int, int>>, vector<pair<double, pair<int, int>>>, greater<pair<double, pair<int, int>>>> pq;
    
    dis[0][0] = 0;
    pq.emplace(0, pair(0, 0));

    while (not pq.empty()) {
        auto w = pq.top().ff;
        auto v = pq.top().ss.ff;
        auto used = pq.top().ss.ss;
        pq.pop();

        // cout << w << " " << v << " " << used << endl;

        if (w != dis[v][used]) continue;
        if (v == H) continue;

        double nw;
        for (int eidx : G[v]) {
            int u = x[eidx] ^ y[eidx] ^ v;
            if (arr[u] == 0) {
                nw = 0;
                if (dis[u][used] > nw) {
                    dis[u][used] = nw;
                    pq.emplace(nw, pair(u, used));
                }
            }
            if (arr[u] == 2 and used < K) {
                nw = (w + c[eidx]) / 2;
                if (dis[u][used + 1] > nw) {
                    dis[u][used + 1] = nw;
                    pq.emplace(nw, pair(u, used + 1));
                }
            }
            nw = w + c[eidx];
            if (dis[u][used] > nw) {
                dis[u][used] = nw;
                pq.emplace(nw, pair(u, used));
            }
        }
    }
    double res = 1e18;
    for (int i = 0; i <= K; ++i) res = min(res, dis[H][i]);
    return (res == 1e18 ? -1 : res);
}

// int main() {
//     freopen("bai3.inp", "r", stdin);
//     freopen("bai3.out", "w", stdout);
//     int T;
//     assert(1 == scanf("%d", &T));
//     while (T--){
//         int N,M,K,H;
//         assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
//         std::vector<int> x(M);
//         std::vector<int> y(M);
//         std::vector<int> c(M);
//         std::vector<int> arr(N);
//         for (int i = 0; i < N; i++) assert(1 == scanf("%d", &arr[i]));
//         for (int i = 0; i < M; i++) assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
//         // if (T == 10000 - 195) {
//         //     cout << N << " " << M << " " << K << " " << H << endl;
//         //     for (int i = 0; i < N; ++i) cout << arr[i] << " \n"[i + 1 == N];
//         //     for (int i = 0; i < M; ++i) cout << x[i] << " " << y[i] << " " << c[i] << "\n";
//         // }
//         printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
//     }
// }

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 856 KB Correct.
2 Correct 19 ms 864 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 1628 KB Correct.
2 Correct 26 ms 1556 KB Correct.
3 Correct 24 ms 1628 KB Correct.
4 Correct 27 ms 1600 KB Correct.
5 Correct 26 ms 1676 KB Correct.
6 Correct 23 ms 4736 KB Correct.
7 Correct 29 ms 4520 KB Correct.
8 Correct 14 ms 8036 KB Correct.
9 Correct 25 ms 1244 KB Correct.
10 Correct 23 ms 1196 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 1384 KB Correct.
2 Correct 26 ms 1724 KB Correct.
3 Correct 26 ms 1744 KB Correct.
4 Correct 26 ms 1376 KB Correct.
5 Correct 26 ms 1316 KB Correct.
6 Correct 6 ms 3424 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 22444 KB Correct.
2 Correct 483 ms 1836 KB Correct.
3 Correct 403 ms 1780 KB Correct.
4 Correct 429 ms 1744 KB Correct.
5 Correct 297 ms 1340 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1504 KB Correct.
2 Correct 24 ms 1372 KB Correct.
3 Correct 24 ms 1560 KB Correct.
4 Correct 25 ms 4312 KB Correct.
5 Correct 21 ms 1112 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1380 KB Correct.
2 Correct 22 ms 1680 KB Correct.
3 Correct 44 ms 29268 KB Correct.
4 Correct 17 ms 3024 KB Correct.
5 Correct 24 ms 1372 KB Correct.
6 Correct 26 ms 1724 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 273 ms 1880 KB Correct.
2 Correct 30 ms 1628 KB Correct.
3 Correct 1345 ms 29332 KB Correct.
4 Correct 997 ms 9316 KB Correct.
5 Correct 690 ms 33336 KB Correct.
6 Correct 301 ms 18116 KB Correct.
7 Correct 986 ms 8836 KB Correct.
8 Correct 972 ms 3120 KB Correct.
9 Correct 236 ms 2112 KB Correct.
10 Correct 250 ms 2424 KB Correct.
11 Correct 906 ms 2764 KB Correct.
12 Correct 255 ms 2264 KB Correct.
13 Correct 241 ms 2148 KB Correct.
14 Correct 865 ms 10540 KB Correct.
15 Correct 1182 ms 4856 KB Correct.
16 Correct 228 ms 2056 KB Correct.
17 Correct 294 ms 2240 KB Correct.
18 Correct 296 ms 2356 KB Correct.
19 Correct 856 ms 3488 KB Correct.
20 Correct 18 ms 604 KB Correct.
21 Correct 21 ms 1072 KB Correct.
22 Correct 23 ms 2348 KB Correct.

Subtask #8
0.0 / 3.0

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