oj.uz

Submission #1069698

# Submission time Handle Problem Language Result Execution time Memory
1069698 2024-08-22T08:22:46 Z thangdz2k7 Cyberland (APIO23_cyberland) C++17
100 / 100
 1559 ms 10588 KB 
#include <bits/stdc++.h>
#define db double

using namespace std;

const db inf = 1e18;
const db mid = 2.0;

db solve(int N, int M, int K, int H, vector <int> x, vector <int> y, vector <int> c, vector <int> arr){
    K = min(K, 100);

    vector <vector <int>> adj(N);
    for (int i = 0; i < M; ++ i) adj[x[i]].push_back(i), adj[y[i]].push_back(i);
    vector <db> dp(N, inf);
    dp[0] = 0.0; db ans = inf;

    for (int loops = 0; loops <= K; ++ loops){
        priority_queue <pair <db, int>> qu;
        vector <db> rd(N, inf);
        for (int u = 0; u < N; ++ u){
            if (dp[u] == inf || (u > 0 && arr[u] == 1)) continue;
            if (arr[u] == 0) rd[u] = 0.0;
            qu.push({-dp[u] / mid, u});
        }

        while (qu.size()){
            auto [du, u] = qu.top();
            qu.pop(); du = -du;
            if (u == H) continue;
            for (int id : adj[u]){
                int v = x[id] ^ y[id] ^ u;
                if (rd[v] > du + c[id]){
                    if (arr[v] == 0) rd[v] = 0;
                    else rd[v] = du + c[id];
                    qu.push({-rd[v], v});
                }
            }
        }

        if (!loops && rd[H] == inf) break;
        dp = rd;
        ans = min(ans, dp[H]);
    }

    if (ans == inf) return -1;
    return ans;
}

//void solve(){
//    int N, M, K; cin >> N >> M >> K;
//    int H; cin >> H;
//    vector <int> arr(N); for (int i = 0; i < N; ++ i) cin >> arr[i];
//    vector <int> x(M), y(M), z(M); for (int i = 0; i < M; ++ i) cin >> x[i] >> y[i] >> z[i];
//    cout << fixed << setprecision(10) << solve(N, M, K, H, x, y, z, arr) << '\n';
//}
//
//int main(){
//    freopen("cyberland.inp", "r", stdin);
//    freopen("cyberland.out", "w", stdout);
////    ios_base::sync_with_stdio(0);
////    cin.tie(0);
////    cout.tie(0);
//
//    int t = 1;
//    while (t --) solve();
//
//    return 0;
//}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 604 KB Correct.
2 Correct 30 ms 600 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 596 KB Correct.
2 Correct 69 ms 592 KB Correct.
3 Correct 65 ms 848 KB Correct.
4 Correct 67 ms 564 KB Correct.
5 Correct 67 ms 592 KB Correct.
6 Correct 153 ms 1416 KB Correct.
7 Correct 189 ms 1408 KB Correct.
8 Correct 93 ms 2552 KB Correct.
9 Correct 55 ms 344 KB Correct.
10 Correct 56 ms 516 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 348 KB Correct.
2 Correct 92 ms 344 KB Correct.
3 Correct 83 ms 584 KB Correct.
4 Correct 77 ms 344 KB Correct.
5 Correct 69 ms 348 KB Correct.
6 Correct 38 ms 1372 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 6800 KB Correct.
2 Correct 94 ms 596 KB Correct.
3 Correct 85 ms 604 KB Correct.
4 Correct 87 ms 552 KB Correct.
5 Correct 55 ms 348 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 592 KB Correct.
2 Correct 43 ms 528 KB Correct.
3 Correct 51 ms 348 KB Correct.
4 Correct 111 ms 1364 KB Correct.
5 Correct 33 ms 344 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 568 KB Correct.
2 Correct 41 ms 604 KB Correct.
3 Correct 30 ms 7804 KB Correct.
4 Correct 66 ms 1156 KB Correct.
5 Correct 51 ms 344 KB Correct.
6 Correct 47 ms 552 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 592 KB Correct.
2 Correct 16 ms 600 KB Correct.
3 Correct 355 ms 10348 KB Correct.
4 Correct 256 ms 2564 KB Correct.
5 Correct 466 ms 7412 KB Correct.
6 Correct 239 ms 4628 KB Correct.
7 Correct 239 ms 2764 KB Correct.
8 Correct 179 ms 820 KB Correct.
9 Correct 73 ms 596 KB Correct.
10 Correct 66 ms 344 KB Correct.
11 Correct 166 ms 604 KB Correct.
12 Correct 83 ms 556 KB Correct.
13 Correct 82 ms 604 KB Correct.
14 Correct 234 ms 5392 KB Correct.
15 Correct 218 ms 1532 KB Correct.
16 Correct 74 ms 592 KB Correct.
17 Correct 96 ms 596 KB Correct.
18 Correct 82 ms 596 KB Correct.
19 Correct 259 ms 592 KB Correct.
20 Correct 5 ms 344 KB Correct.
21 Correct 5 ms 348 KB Correct.
22 Correct 15 ms 860 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 588 KB Correct.
2 Correct 39 ms 344 KB Correct.
3 Correct 256 ms 10588 KB Correct.
4 Correct 272 ms 3264 KB Correct.
5 Correct 1508 ms 8992 KB Correct.
6 Correct 778 ms 6388 KB Correct.
7 Correct 624 ms 6516 KB Correct.
8 Correct 219 ms 2640 KB Correct.
9 Correct 157 ms 1340 KB Correct.
10 Correct 148 ms 1364 KB Correct.
11 Correct 223 ms 1708 KB Correct.
12 Correct 181 ms 1536 KB Correct.
13 Correct 179 ms 1556 KB Correct.
14 Correct 1559 ms 7008 KB Correct.
15 Correct 1117 ms 7608 KB Correct.
16 Correct 412 ms 3936 KB Correct.
17 Correct 255 ms 2704 KB Correct.
18 Correct 184 ms 1388 KB Correct.
19 Correct 213 ms 1452 KB Correct.
20 Correct 175 ms 1360 KB Correct.
21 Correct 617 ms 2452 KB Correct.
22 Correct 13 ms 344 KB Correct.
23 Correct 11 ms 348 KB Correct.
24 Correct 50 ms 860 KB Correct.