oj.uz

Submission #1069706

# Submission time Handle Problem Language Result Execution time Memory
1069706 2024-08-22T08:25:29 Z thangdz2k7 Cyberland (APIO23_cyberland) C++17
100 / 100
 1478 ms 10576 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]) rd[v] = 0.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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 856 KB Correct.
2 Correct 22 ms 588 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 576 KB Correct.
2 Correct 73 ms 580 KB Correct.
3 Correct 73 ms 572 KB Correct.
4 Correct 106 ms 812 KB Correct.
5 Correct 87 ms 552 KB Correct.
6 Correct 150 ms 1416 KB Correct.
7 Correct 204 ms 1328 KB Correct.
8 Correct 89 ms 2492 KB Correct.
9 Correct 84 ms 348 KB Correct.
10 Correct 55 ms 344 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 540 KB Correct.
2 Correct 102 ms 564 KB Correct.
3 Correct 86 ms 592 KB Correct.
4 Correct 72 ms 348 KB Correct.
5 Correct 70 ms 524 KB Correct.
6 Correct 39 ms 1372 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 6536 KB Correct.
2 Correct 115 ms 600 KB Correct.
3 Correct 88 ms 564 KB Correct.
4 Correct 91 ms 596 KB Correct.
5 Correct 58 ms 524 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 596 KB Correct.
2 Correct 43 ms 344 KB Correct.
3 Correct 45 ms 348 KB Correct.
4 Correct 121 ms 1364 KB Correct.
5 Correct 44 ms 528 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 592 KB Correct.
2 Correct 58 ms 592 KB Correct.
3 Correct 35 ms 7764 KB Correct.
4 Correct 66 ms 1204 KB Correct.
5 Correct 70 ms 344 KB Correct.
6 Correct 53 ms 344 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 552 KB Correct.
2 Correct 16 ms 344 KB Correct.
3 Correct 356 ms 10344 KB Correct.
4 Correct 285 ms 2564 KB Correct.
5 Correct 506 ms 7216 KB Correct.
6 Correct 286 ms 4640 KB Correct.
7 Correct 259 ms 2764 KB Correct.
8 Correct 201 ms 768 KB Correct.
9 Correct 84 ms 560 KB Correct.
10 Correct 76 ms 568 KB Correct.
11 Correct 199 ms 560 KB Correct.
12 Correct 104 ms 568 KB Correct.
13 Correct 92 ms 560 KB Correct.
14 Correct 239 ms 5328 KB Correct.
15 Correct 236 ms 1532 KB Correct.
16 Correct 106 ms 600 KB Correct.
17 Correct 101 ms 580 KB Correct.
18 Correct 102 ms 580 KB Correct.
19 Correct 272 ms 348 KB Correct.
20 Correct 8 ms 348 KB Correct.
21 Correct 6 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 188 ms 592 KB Correct.
2 Correct 39 ms 344 KB Correct.
3 Correct 221 ms 10576 KB Correct.
4 Correct 267 ms 976 KB Correct.
5 Correct 1478 ms 7208 KB Correct.
6 Correct 727 ms 4628 KB Correct.
7 Correct 612 ms 4216 KB Correct.
8 Correct 222 ms 596 KB Correct.
9 Correct 159 ms 584 KB Correct.
10 Correct 142 ms 596 KB Correct.
11 Correct 223 ms 508 KB Correct.
12 Correct 174 ms 596 KB Correct.
13 Correct 179 ms 552 KB Correct.
14 Correct 1441 ms 5544 KB Correct.
15 Correct 1040 ms 5496 KB Correct.
16 Correct 398 ms 2060 KB Correct.
17 Correct 247 ms 816 KB Correct.
18 Correct 159 ms 592 KB Correct.
19 Correct 209 ms 568 KB Correct.
20 Correct 178 ms 592 KB Correct.
21 Correct 563 ms 592 KB Correct.
22 Correct 11 ms 344 KB Correct.
23 Correct 11 ms 512 KB Correct.
24 Correct 42 ms 860 KB Correct.