Submission #969394

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
969394	2024-04-25T05:49:53 Z	CDuong	Cyberland (APIO23_cyberland)	C++17	97 / 100	1345 ms	2097152 KB

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) {
    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

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	856 KB	Correct.
2	Correct	19 ms	864 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1257 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Submission #969394

Compilation message