oj.uz

Submission #1034316

# Submission time Handle Problem Language Result Execution time Memory
1034316 2024-07-25T12:14:43 Z Zero_OP Cyberland (APIO23_cyberland) C++17
100 / 100
 944 ms 67280 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, 67);
    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({0, 0, 0});
    for(int k = 0; k <= K; ++k){
        priority_queue<node, vector<node>, greater<node>> tmp;
        while(!pq.empty()){
            auto [tot, u, k] = pq.top(); pq.pop();
            if(d[k][u] != tot || u == H) continue;
            for(auto [v, w] : adj[u]){
                if(arr[v] == 0 && d[k][v] > 0){
                    d[k][v] = 0;
                    pq.push({d[k][v], v, k});
                }

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

                if(arr[v] == 2 && k < K && (tot + w) / 2.0 < d[k + 1][v]){
                    d[k + 1][v] = (tot + w) / 2.0;
                    tmp.push({d[k + 1][v], v, k + 1});
                }
            }
        }

        swap(pq, tmp);
    }

    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 43 ms 852 KB Correct.
2 Correct 53 ms 848 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1884 KB Correct.
2 Correct 26 ms 1760 KB Correct.
3 Correct 33 ms 1880 KB Correct.
4 Correct 25 ms 1764 KB Correct.
5 Correct 29 ms 1900 KB Correct.
6 Correct 23 ms 7356 KB Correct.
7 Correct 31 ms 7240 KB Correct.
8 Correct 15 ms 13852 KB Correct.
9 Correct 21 ms 1316 KB Correct.
10 Correct 20 ms 1372 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1948 KB Correct.
2 Correct 34 ms 1800 KB Correct.
3 Correct 29 ms 1836 KB Correct.
4 Correct 23 ms 1400 KB Correct.
5 Correct 23 ms 1368 KB Correct.
6 Correct 6 ms 5724 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 39256 KB Correct.
2 Correct 90 ms 1780 KB Correct.
3 Correct 103 ms 1992 KB Correct.
4 Correct 83 ms 1824 KB Correct.
5 Correct 53 ms 1396 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1824 KB Correct.
2 Correct 47 ms 1744 KB Correct.
3 Correct 24 ms 1864 KB Correct.
4 Correct 24 ms 6996 KB Correct.
5 Correct 19 ms 1372 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2192 KB Correct.
2 Correct 27 ms 1836 KB Correct.
3 Correct 58 ms 51024 KB Correct.
4 Correct 20 ms 4716 KB Correct.
5 Correct 24 ms 1216 KB Correct.
6 Correct 24 ms 1872 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 1820 KB Correct.
2 Correct 17 ms 1624 KB Correct.
3 Correct 357 ms 64024 KB Correct.
4 Correct 275 ms 16060 KB Correct.
5 Correct 383 ms 28508 KB Correct.
6 Correct 179 ms 12064 KB Correct.
7 Correct 262 ms 16620 KB Correct.
8 Correct 196 ms 3464 KB Correct.
9 Correct 82 ms 1972 KB Correct.
10 Correct 90 ms 1996 KB Correct.
11 Correct 165 ms 2320 KB Correct.
12 Correct 93 ms 1792 KB Correct.
13 Correct 90 ms 1856 KB Correct.
14 Correct 255 ms 32020 KB Correct.
15 Correct 236 ms 9660 KB Correct.
16 Correct 88 ms 1924 KB Correct.
17 Correct 109 ms 1868 KB Correct.
18 Correct 97 ms 1824 KB Correct.
19 Correct 295 ms 2360 KB Correct.
20 Correct 6 ms 600 KB Correct.
21 Correct 9 ms 1036 KB Correct.
22 Correct 15 ms 1372 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 1836 KB Correct.
2 Correct 30 ms 1624 KB Correct.
3 Correct 197 ms 67280 KB Correct.
4 Correct 275 ms 5916 KB Correct.
5 Correct 768 ms 28540 KB Correct.
6 Correct 359 ms 12320 KB Correct.
7 Correct 447 ms 25564 KB Correct.
8 Correct 207 ms 2396 KB Correct.
9 Correct 127 ms 1752 KB Correct.
10 Correct 125 ms 1696 KB Correct.
11 Correct 178 ms 1620 KB Correct.
12 Correct 145 ms 2052 KB Correct.
13 Correct 134 ms 2060 KB Correct.
14 Correct 944 ms 28648 KB Correct.
15 Correct 726 ms 34732 KB Correct.
16 Correct 354 ms 13152 KB Correct.
17 Correct 209 ms 4320 KB Correct.
18 Correct 116 ms 2144 KB Correct.
19 Correct 146 ms 2208 KB Correct.
20 Correct 135 ms 2132 KB Correct.
21 Correct 457 ms 3116 KB Correct.
22 Correct 8 ms 604 KB Correct.
23 Correct 9 ms 988 KB Correct.
24 Correct 25 ms 1372 KB Correct.