Submission #969397

#	Time	Username	Problem	Language	Result	Execution time	Memory
969397		CDuong	Cyberland (APIO23_cyberland)	C++17	97 / 100	3056 ms	93564 KiB

cyberland

#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) {
    K = min(K, 70);

    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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 0 / 3