oj.uz

Submission #1034302

# Submission time Handle Problem Language Result Execution time Memory
1034302 2024-07-25T11:59:11 Z Zero_OP Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 92520 KB 
#include<bits/stdc++.h>
#ifndef HOME
    #include "cyberland.h"
    //including problem's library
#endif //HOME

using namespace std;

#define          left __left
#define         right __right
#define          next __next
#define          prev __prev
#define           div __div
#define            pb push_back
#define            pf push_front
#define        all(v) v.begin(), v.end()
#define         sz(v) (int)v.size()
#define    compact(v) v.erase(unique(all(v)), end(v))
#define        dbg(v) "[" #v " = " << (v) << "]"
#define    file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b) return a = b, true;
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b) return a = b, true;
        return false;
    }

template<int dimension, typename T>
struct vec : public vector<vec<dimension - 1, T>> {
    static_assert(dimension > 0, "Dimension must be positive !\n");
    template<typename... Args>
    vec(int n = 0, Args... args) : vector<vec<dimension - 1, T>> (n, vec<dimension - 1, T>(args...)) {}
};

template<typename T>
struct vec<1, T> : public vector<T> {
    vec(int n = 0, T val = T()) : vector<T>(n, val) {}
};

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
    vector<vector<pair<int, int>>> adj(N);
    for(int i = 0; i < M; ++i){
        int u = x[i], v = y[i], w = c[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    K = min(K, 70);
    using node = tuple<double, int, int>;
    const double inf = 1e18;
    priority_queue<node, vector<node>, greater<node>> pq;
    vector<vector<double>> d(71, vector<double>(N, inf));
    d[0][0] = 0;
    pq.push({d[0][0], 0, 0});

    while(!pq.empty()){
        double tots; int u, k;
        tie(tots, u, k) = pq.top();
        pq.pop();

        if(d[k][u] != tots) continue;
        if(u == H) continue;

        for(auto [v, w] : adj[u]){
            if(arr[v] == 0 && d[k][v] > 0){ //apply operation 1
                d[k][v] = 0;
                pq.push({d[k][v], v, k});
            }

            if(d[k][v] > d[k][u] + w){ //not apply any operations
                d[k][v] = d[k][u] + w;
                pq.push({d[k][v], v, k});
            }

            if(k < K && arr[v] == 2 && d[k + 1][v] > (d[k][u] + w) / 2.0){ //apply operation 2
                d[k + 1][v] = (d[k][u] + w) / 2.0;
                pq.push({d[k + 1][v], v, k + 1});
            }
        }
    }

    double ans = inf;
    for(int i = 0; i <= K; ++i){
        ans = min(ans, d[i][H]);
    }

    return ans == inf ? -1 : ans;
}

#ifdef HOME
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cout << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1}) << '\n';
    cout << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1}) << '\n';

    return 0;
}
#endif // HOME

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 848 KB Correct.
2 Correct 51 ms 836 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1960 KB Correct.
2 Correct 26 ms 2304 KB Correct.
3 Correct 31 ms 2244 KB Correct.
4 Correct 30 ms 2100 KB Correct.
5 Correct 28 ms 2136 KB Correct.
6 Correct 24 ms 7672 KB Correct.
7 Correct 33 ms 7500 KB Correct.
8 Correct 14 ms 13844 KB Correct.
9 Correct 31 ms 1544 KB Correct.
10 Correct 24 ms 1372 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2112 KB Correct.
2 Correct 33 ms 1976 KB Correct.
3 Correct 29 ms 1964 KB Correct.
4 Correct 30 ms 1408 KB Correct.
5 Correct 22 ms 1368 KB Correct.
6 Correct 10 ms 5724 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 39520 KB Correct.
2 Correct 480 ms 2036 KB Correct.
3 Correct 382 ms 2144 KB Correct.
4 Correct 411 ms 2108 KB Correct.
5 Correct 298 ms 1536 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1932 KB Correct.
2 Correct 24 ms 2000 KB Correct.
3 Correct 25 ms 2360 KB Correct.
4 Correct 24 ms 7268 KB Correct.
5 Correct 19 ms 1368 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2116 KB Correct.
2 Correct 23 ms 1964 KB Correct.
3 Correct 47 ms 51712 KB Correct.
4 Correct 19 ms 4792 KB Correct.
5 Correct 22 ms 1424 KB Correct.
6 Correct 38 ms 2128 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 2436 KB Correct.
2 Correct 29 ms 1696 KB Correct.
3 Correct 1296 ms 65896 KB Correct.
4 Correct 1065 ms 16656 KB Correct.
5 Correct 696 ms 43616 KB Correct.
6 Correct 277 ms 20228 KB Correct.
7 Correct 1024 ms 17312 KB Correct.
8 Correct 1022 ms 4152 KB Correct.
9 Correct 241 ms 2328 KB Correct.
10 Correct 275 ms 2460 KB Correct.
11 Correct 940 ms 3012 KB Correct.
12 Correct 255 ms 2432 KB Correct.
13 Correct 245 ms 2416 KB Correct.
14 Correct 852 ms 32420 KB Correct.
15 Correct 1226 ms 9988 KB Correct.
16 Correct 240 ms 2364 KB Correct.
17 Correct 278 ms 2592 KB Correct.
18 Correct 305 ms 2464 KB Correct.
19 Correct 859 ms 3180 KB Correct.
20 Correct 18 ms 604 KB Correct.
21 Correct 20 ms 1176 KB Correct.
22 Correct 22 ms 2512 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 3504 KB Correct.
2 Correct 73 ms 2916 KB Correct.
3 Correct 513 ms 67136 KB Correct.
4 Correct 2282 ms 5860 KB Correct.
5 Correct 1967 ms 92520 KB Correct.
6 Correct 696 ms 44252 KB Correct.
7 Execution timed out 3016 ms 31756 KB Time limit exceeded
8 Halted 0 ms 0 KB -