oj.uz

Submission #1069694

# Submission time Handle Problem Language Result Execution time Memory
1069694 2024-08-22T08:21:36 Z thangdz2k7 Cyberland (APIO23_cyberland) C++17
97 / 100
 477 ms 10576 KB 
#include <bits/stdc++.h>
#define db double

using namespace std;

const db inf = 1e12;
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 25 ms 580 KB Correct.
2 Correct 22 ms 604 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 87 ms 348 KB Correct.
4 Correct 68 ms 560 KB Correct.
5 Correct 74 ms 564 KB Correct.
6 Correct 143 ms 1412 KB Correct.
7 Correct 189 ms 1316 KB Correct.
8 Correct 89 ms 2492 KB Correct.
9 Correct 57 ms 504 KB Correct.
10 Correct 56 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 344 KB Correct.
2 Correct 89 ms 348 KB Correct.
3 Correct 86 ms 616 KB Correct.
4 Correct 78 ms 516 KB Correct.
5 Correct 71 ms 516 KB Correct.
6 Correct 39 ms 1368 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 6800 KB Correct.
2 Correct 99 ms 1616 KB Correct.
3 Correct 81 ms 1384 KB Correct.
4 Correct 87 ms 1444 KB Correct.
5 Correct 59 ms 1392 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 596 KB Correct.
2 Correct 43 ms 344 KB Correct.
3 Correct 44 ms 344 KB Correct.
4 Correct 113 ms 1364 KB Correct.
5 Correct 34 ms 344 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 596 KB Correct.
2 Correct 49 ms 600 KB Correct.
3 Correct 29 ms 7772 KB Correct.
4 Correct 65 ms 1164 KB Correct.
5 Correct 41 ms 348 KB Correct.
6 Correct 47 ms 588 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 604 KB Correct.
2 Correct 16 ms 348 KB Correct.
3 Correct 321 ms 10300 KB Correct.
4 Correct 254 ms 4872 KB Correct.
5 Correct 477 ms 9104 KB Correct.
6 Correct 237 ms 6144 KB Correct.
7 Correct 239 ms 2788 KB Correct.
8 Correct 185 ms 2868 KB Correct.
9 Correct 74 ms 592 KB Correct.
10 Correct 67 ms 1324 KB Correct.
11 Correct 162 ms 2528 KB Correct.
12 Correct 83 ms 1616 KB Correct.
13 Correct 85 ms 1388 KB Correct.
14 Correct 232 ms 6856 KB Correct.
15 Correct 209 ms 3584 KB Correct.
16 Correct 74 ms 1360 KB Correct.
17 Correct 95 ms 1620 KB Correct.
18 Correct 87 ms 1360 KB Correct.
19 Correct 260 ms 2388 KB Correct.
20 Correct 7 ms 344 KB Correct.
21 Correct 6 ms 348 KB Correct.
22 Correct 16 ms 860 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 592 KB Correct.
2 Correct 38 ms 348 KB Correct.
3 Incorrect 32 ms 10576 KB Wrong Answer.
4 Halted 0 ms 0 KB -