oj.uz

Submission #1034306

# Submission time Handle Problem Language Result Execution time Memory
1034306 2024-07-25T12:01:34 Z Zero_OP Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 91864 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, 66);
    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 37 ms 600 KB Correct.
2 Correct 38 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1176 KB Correct.
2 Correct 34 ms 1272 KB Correct.
3 Correct 24 ms 1064 KB Correct.
4 Correct 32 ms 1084 KB Correct.
5 Correct 33 ms 1160 KB Correct.
6 Correct 22 ms 6684 KB Correct.
7 Correct 29 ms 6724 KB Correct.
8 Correct 15 ms 13404 KB Correct.
9 Correct 18 ms 676 KB Correct.
10 Correct 19 ms 604 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1104 KB Correct.
2 Correct 27 ms 1116 KB Correct.
3 Correct 22 ms 1144 KB Correct.
4 Correct 20 ms 604 KB Correct.
5 Correct 20 ms 676 KB Correct.
6 Correct 5 ms 5720 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 40708 KB Correct.
2 Correct 176 ms 1260 KB Correct.
3 Correct 153 ms 1308 KB Correct.
4 Correct 158 ms 1204 KB Correct.
5 Correct 133 ms 680 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1236 KB Correct.
2 Correct 41 ms 1076 KB Correct.
3 Correct 21 ms 1084 KB Correct.
4 Correct 22 ms 6744 KB Correct.
5 Correct 18 ms 604 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1140 KB Correct.
2 Correct 20 ms 1100 KB Correct.
3 Correct 44 ms 50052 KB Correct.
4 Correct 19 ms 4588 KB Correct.
5 Correct 21 ms 668 KB Correct.
6 Correct 20 ms 1096 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 1340 KB Correct.
2 Correct 24 ms 1696 KB Correct.
3 Correct 638 ms 65212 KB Correct.
4 Correct 468 ms 15092 KB Correct.
5 Correct 725 ms 59036 KB Correct.
6 Correct 341 ms 26884 KB Correct.
7 Correct 484 ms 16396 KB Correct.
8 Correct 475 ms 3004 KB Correct.
9 Correct 149 ms 1452 KB Correct.
10 Correct 145 ms 1508 KB Correct.
11 Correct 452 ms 1280 KB Correct.
12 Correct 161 ms 1476 KB Correct.
13 Correct 190 ms 1588 KB Correct.
14 Correct 406 ms 31556 KB Correct.
15 Correct 461 ms 8456 KB Correct.
16 Correct 155 ms 1452 KB Correct.
17 Correct 201 ms 1544 KB Correct.
18 Correct 161 ms 1388 KB Correct.
19 Correct 390 ms 1548 KB Correct.
20 Correct 13 ms 604 KB Correct.
21 Correct 12 ms 1040 KB Correct.
22 Correct 26 ms 3536 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 2708 KB Correct.
2 Correct 74 ms 3916 KB Correct.
3 Correct 460 ms 66776 KB Correct.
4 Correct 984 ms 4684 KB Correct.
5 Correct 2619 ms 91864 KB Correct.
6 Correct 1323 ms 76316 KB Correct.
7 Correct 1113 ms 24632 KB Correct.
8 Correct 1144 ms 3340 KB Correct.
9 Correct 506 ms 4064 KB Correct.
10 Correct 484 ms 4684 KB Correct.
11 Execution timed out 3019 ms 1280 KB Time limit exceeded
12 Halted 0 ms 0 KB -