oj.uz

Submission #1034311

# Submission time Handle Problem Language Result Execution time Memory
1034311 2024-07-25T12:06:43 Z Zero_OP Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 91752 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));
    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 && visited[v]){
            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 43 ms 592 KB Correct.
2 Correct 40 ms 348 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1172 KB Correct.
2 Correct 22 ms 1104 KB Correct.
3 Correct 23 ms 1060 KB Correct.
4 Correct 23 ms 1296 KB Correct.
5 Correct 24 ms 1248 KB Correct.
6 Correct 25 ms 6712 KB Correct.
7 Correct 30 ms 6728 KB Correct.
8 Correct 15 ms 13404 KB Correct.
9 Correct 21 ms 668 KB Correct.
10 Correct 22 ms 604 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1092 KB Correct.
2 Correct 28 ms 1112 KB Correct.
3 Correct 24 ms 1156 KB Correct.
4 Correct 24 ms 604 KB Correct.
5 Correct 23 ms 604 KB Correct.
6 Correct 6 ms 5748 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 40580 KB Correct.
2 Correct 190 ms 1260 KB Correct.
3 Correct 158 ms 1248 KB Correct.
4 Correct 166 ms 1252 KB Correct.
5 Correct 157 ms 684 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1424 KB Correct.
2 Correct 26 ms 1132 KB Correct.
3 Correct 24 ms 1100 KB Correct.
4 Correct 24 ms 6744 KB Correct.
5 Correct 19 ms 600 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1140 KB Correct.
2 Correct 20 ms 1104 KB Correct.
3 Correct 46 ms 50004 KB Correct.
4 Correct 18 ms 4588 KB Correct.
5 Correct 24 ms 636 KB Correct.
6 Correct 23 ms 1060 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 1332 KB Correct.
2 Correct 26 ms 1768 KB Correct.
3 Correct 491 ms 65172 KB Correct.
4 Correct 463 ms 15052 KB Correct.
5 Correct 682 ms 59036 KB Correct.
6 Correct 292 ms 27124 KB Correct.
7 Correct 448 ms 16584 KB Correct.
8 Correct 441 ms 2828 KB Correct.
9 Correct 148 ms 1452 KB Correct.
10 Correct 144 ms 1628 KB Correct.
11 Correct 464 ms 1456 KB Correct.
12 Correct 156 ms 1492 KB Correct.
13 Correct 158 ms 1600 KB Correct.
14 Correct 402 ms 31552 KB Correct.
15 Correct 422 ms 8620 KB Correct.
16 Correct 142 ms 1432 KB Correct.
17 Correct 177 ms 1528 KB Correct.
18 Correct 169 ms 1344 KB Correct.
19 Correct 372 ms 1500 KB Correct.
20 Correct 13 ms 600 KB Correct.
21 Correct 11 ms 1132 KB Correct.
22 Correct 25 ms 3536 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 2656 KB Correct.
2 Correct 74 ms 3864 KB Correct.
3 Correct 460 ms 66624 KB Correct.
4 Correct 961 ms 4712 KB Correct.
5 Correct 2347 ms 91752 KB Correct.
6 Correct 1136 ms 76180 KB Correct.
7 Correct 1000 ms 24356 KB Correct.
8 Correct 1012 ms 2056 KB Correct.
9 Correct 489 ms 3968 KB Correct.
10 Correct 479 ms 4056 KB Correct.
11 Execution timed out 3021 ms 516 KB Time limit exceeded
12 Halted 0 ms 0 KB -