oj.uz

Submission #1034298

# Submission time Handle Problem Language Result Execution time Memory
1034298 2024-07-25T11:57:14 Z Zero_OP Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 93544 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 39 ms 848 KB Correct.
2 Correct 43 ms 800 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1972 KB Correct.
2 Correct 27 ms 2184 KB Correct.
3 Correct 32 ms 2072 KB Correct.
4 Correct 27 ms 2108 KB Correct.
5 Correct 26 ms 2196 KB Correct.
6 Correct 24 ms 7740 KB Correct.
7 Correct 31 ms 7496 KB Correct.
8 Correct 15 ms 13916 KB Correct.
9 Correct 22 ms 1544 KB Correct.
10 Correct 21 ms 1568 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2136 KB Correct.
2 Correct 27 ms 1984 KB Correct.
3 Correct 25 ms 2068 KB Correct.
4 Correct 23 ms 1372 KB Correct.
5 Correct 23 ms 1372 KB Correct.
6 Correct 6 ms 5980 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 41920 KB Correct.
2 Correct 194 ms 2184 KB Correct.
3 Correct 158 ms 2268 KB Correct.
4 Correct 167 ms 2172 KB Correct.
5 Correct 151 ms 1620 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1936 KB Correct.
2 Correct 25 ms 2032 KB Correct.
3 Correct 30 ms 2072 KB Correct.
4 Correct 24 ms 7252 KB Correct.
5 Correct 18 ms 1368 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2068 KB Correct.
2 Correct 28 ms 2116 KB Correct.
3 Correct 49 ms 51804 KB Correct.
4 Correct 18 ms 5016 KB Correct.
5 Correct 22 ms 1536 KB Correct.
6 Correct 23 ms 2048 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 2300 KB Correct.
2 Correct 26 ms 1916 KB Correct.
3 Correct 541 ms 67236 KB Correct.
4 Correct 460 ms 17412 KB Correct.
5 Correct 669 ms 60800 KB Correct.
6 Correct 283 ms 28516 KB Correct.
7 Correct 398 ms 17600 KB Correct.
8 Correct 435 ms 4360 KB Correct.
9 Correct 152 ms 2200 KB Correct.
10 Correct 147 ms 2484 KB Correct.
11 Correct 427 ms 3100 KB Correct.
12 Correct 162 ms 2652 KB Correct.
13 Correct 174 ms 2580 KB Correct.
14 Correct 338 ms 32836 KB Correct.
15 Correct 442 ms 10456 KB Correct.
16 Correct 146 ms 2360 KB Correct.
17 Correct 183 ms 2568 KB Correct.
18 Correct 174 ms 2368 KB Correct.
19 Correct 400 ms 3476 KB Correct.
20 Correct 14 ms 860 KB Correct.
21 Correct 12 ms 1400 KB Correct.
22 Correct 25 ms 3536 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 3736 KB Correct.
2 Correct 69 ms 4108 KB Correct.
3 Correct 405 ms 69184 KB Correct.
4 Correct 898 ms 6676 KB Correct.
5 Correct 2321 ms 93544 KB Correct.
6 Correct 1114 ms 77752 KB Correct.
7 Correct 1038 ms 26720 KB Correct.
8 Correct 1058 ms 4100 KB Correct.
9 Correct 496 ms 4564 KB Correct.
10 Correct 428 ms 4940 KB Correct.
11 Execution timed out 3070 ms 1728 KB Time limit exceeded
12 Halted 0 ms 0 KB -