oj.uz

Submission #1034295

# Submission time Handle Problem Language Result Execution time Memory
1034295 2024-07-25T11:54:18 Z Zero_OP Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 92956 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, 68);
    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));
    vector<bool> visited(N);

    auto dfs = [&](auto &self, int u){
        visited[u] = true;
        if(u == H) return;
        for(auto [v, w] : adj[u]) if(!visited[v]){
            self(self, v);
        }
    };

    dfs(dfs, 0);
    if(!visited[H]) return -1;

    for(int i = 0; i < N; ++i){
        if(visited[i] && arr[i] == 0){
            d[0][i] = 0;
            pq.push({d[0][i], 0, i});
        }
    }

    d[0][0] = 0;
    pq.push({d[0][0], 0, 0});
    while(!pq.empty()){
        double tot; int k, u;
        tie(tot, k, u) = pq.top();
        pq.pop();

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

        for(auto [v, w] : adj[u]) if(arr[v] != 0){
            if(arr[v] == 2 && k < K && d[k + 1][v] > (tot + w) / 2.0){
                d[k + 1][v] = (tot + w) / 2.0;
                pq.push({d[k + 1][v], k + 1, v});
            }
            if(d[k][v] > d[k][u] + w){
                d[k][v] = d[k][u] + w;
                pq.push({d[k][v], k, v});
            }
        }
    }

    double ans = inf;
    for(int i = 0; i <= K; ++i){
        ans = min(ans, d[i][H]);
    }
    return 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 41 ms 852 KB Correct.
2 Correct 40 ms 852 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1712 KB Correct.
2 Correct 27 ms 2100 KB Correct.
3 Correct 25 ms 1892 KB Correct.
4 Correct 27 ms 1820 KB Correct.
5 Correct 26 ms 1948 KB Correct.
6 Correct 24 ms 7232 KB Correct.
7 Correct 32 ms 7240 KB Correct.
8 Correct 15 ms 13916 KB Correct.
9 Correct 24 ms 1116 KB Correct.
10 Correct 22 ms 1112 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1924 KB Correct.
2 Correct 27 ms 1724 KB Correct.
3 Correct 25 ms 1832 KB Correct.
4 Correct 23 ms 1240 KB Correct.
5 Correct 23 ms 1116 KB Correct.
6 Correct 6 ms 5980 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 41864 KB Correct.
2 Correct 186 ms 1884 KB Correct.
3 Correct 164 ms 2312 KB Correct.
4 Correct 167 ms 1876 KB Correct.
5 Correct 148 ms 1356 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1676 KB Correct.
2 Correct 28 ms 1736 KB Correct.
3 Correct 25 ms 1772 KB Correct.
4 Correct 25 ms 7000 KB Correct.
5 Correct 19 ms 1052 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1804 KB Correct.
2 Correct 21 ms 1704 KB Correct.
3 Correct 44 ms 51280 KB Correct.
4 Correct 19 ms 5020 KB Correct.
5 Correct 22 ms 1472 KB Correct.
6 Correct 24 ms 1812 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 2028 KB Correct.
2 Correct 26 ms 1912 KB Correct.
3 Correct 549 ms 67056 KB Correct.
4 Correct 466 ms 16652 KB Correct.
5 Correct 648 ms 60300 KB Correct.
6 Correct 314 ms 28156 KB Correct.
7 Correct 412 ms 17112 KB Correct.
8 Correct 436 ms 3820 KB Correct.
9 Correct 143 ms 1980 KB Correct.
10 Correct 153 ms 2260 KB Correct.
11 Correct 416 ms 2476 KB Correct.
12 Correct 158 ms 2248 KB Correct.
13 Correct 168 ms 2152 KB Correct.
14 Correct 347 ms 32580 KB Correct.
15 Correct 466 ms 9756 KB Correct.
16 Correct 146 ms 2092 KB Correct.
17 Correct 187 ms 2088 KB Correct.
18 Correct 177 ms 2220 KB Correct.
19 Correct 378 ms 2728 KB Correct.
20 Correct 13 ms 836 KB Correct.
21 Correct 12 ms 1192 KB Correct.
22 Correct 25 ms 3532 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 3460 KB Correct.
2 Correct 79 ms 4076 KB Correct.
3 Correct 460 ms 68436 KB Correct.
4 Correct 921 ms 5904 KB Correct.
5 Correct 2319 ms 92956 KB Correct.
6 Correct 1140 ms 77288 KB Correct.
7 Correct 1014 ms 25624 KB Correct.
8 Correct 1063 ms 3276 KB Correct.
9 Correct 472 ms 4368 KB Correct.
10 Correct 451 ms 4696 KB Correct.
11 Execution timed out 3054 ms 1264 KB Time limit exceeded
12 Halted 0 ms 0 KB -