oj.uz

Submission #920301

# Submission time Handle Problem Language Result Execution time Memory
920301 2024-02-02T12:28:52 Z NotLinux Cyberland (APIO23_cyberland) C++17
100 / 100
 852 ms 10828 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;
const double INF = 1e18;
struct Data{
    int u;
    double w;
    Data(int _u, double _w) : u(_u), w(_w) {}
    friend bool operator <(Data a, Data b){
        return a.w > b.w;
    }
};
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>>>e(n);
    for(int i = 0; i < m; i++){
        e[x[i]].emplace_back(y[i], c[i]);
        e[y[i]].emplace_back(x[i], c[i]);
    }
    priority_queue<Data>q;
    vector<double>d(n, INF);
    q.emplace(0, d[0] = 0.0);
    double ans = INF;
    for(int i = min(k, 80); i > -1; i--){
        vector<double>D(n, INF);
        priority_queue<Data>Q;
        while(!q.empty()){
            auto [u, w] = q.top();
            q.pop();
            if(w > d[u] || u == h){
                continue;
            }
            for(auto& [v, weight] : e[u]){
                if(arr[v] == 0){
                    if(d[v] > 0.0){
                        q.emplace(v, d[v] = 0.0);
                    }
                }
                else{
                    double W = w + double(weight);
                    if(W < d[v]){
                        q.emplace(v, d[v] = W);
                    }
                    if(arr[v] == 2 && i > 0 && (W /= 2.0) < D[v]){
                        Q.emplace(v, D[v] = W);
                    }
                }
            }
        }
        if(ans > d[h])ans = d[h];
        d = D;
        q = Q;
    }
    return ans == INF ? -1 : ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 800 KB Correct.
2 Correct 21 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 600 KB Correct.
2 Correct 22 ms 604 KB Correct.
3 Correct 21 ms 600 KB Correct.
4 Correct 22 ms 604 KB Correct.
5 Correct 22 ms 592 KB Correct.
6 Correct 21 ms 1436 KB Correct.
7 Correct 23 ms 1436 KB Correct.
8 Correct 10 ms 2648 KB Correct.
9 Correct 22 ms 344 KB Correct.
10 Correct 21 ms 344 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 344 KB Correct.
2 Correct 23 ms 856 KB Correct.
3 Correct 21 ms 604 KB Correct.
4 Correct 27 ms 600 KB Correct.
5 Correct 23 ms 348 KB Correct.
6 Correct 5 ms 1112 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 6528 KB Correct.
2 Correct 78 ms 604 KB Correct.
3 Correct 68 ms 600 KB Correct.
4 Correct 74 ms 596 KB Correct.
5 Correct 50 ms 344 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 600 KB Correct.
2 Correct 22 ms 344 KB Correct.
3 Correct 21 ms 600 KB Correct.
4 Correct 19 ms 1112 KB Correct.
5 Correct 19 ms 344 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 600 KB Correct.
2 Correct 19 ms 600 KB Correct.
3 Correct 33 ms 8500 KB Correct.
4 Correct 13 ms 1204 KB Correct.
5 Correct 22 ms 344 KB Correct.
6 Correct 21 ms 836 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 592 KB Correct.
2 Correct 14 ms 604 KB Correct.
3 Correct 290 ms 10828 KB Correct.
4 Correct 191 ms 2564 KB Correct.
5 Correct 328 ms 7888 KB Correct.
6 Correct 153 ms 5428 KB Correct.
7 Correct 195 ms 2764 KB Correct.
8 Correct 157 ms 672 KB Correct.
9 Correct 75 ms 600 KB Correct.
10 Correct 75 ms 592 KB Correct.
11 Correct 140 ms 600 KB Correct.
12 Correct 89 ms 592 KB Correct.
13 Correct 83 ms 868 KB Correct.
14 Correct 185 ms 5576 KB Correct.
15 Correct 178 ms 1624 KB Correct.
16 Correct 81 ms 592 KB Correct.
17 Correct 99 ms 864 KB Correct.
18 Correct 96 ms 816 KB Correct.
19 Correct 248 ms 344 KB Correct.
20 Correct 6 ms 344 KB Correct.
21 Correct 7 ms 600 KB Correct.
22 Correct 12 ms 860 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 536 KB Correct.
2 Correct 32 ms 600 KB Correct.
3 Correct 108 ms 10576 KB Correct.
4 Correct 226 ms 1144 KB Correct.
5 Correct 783 ms 7728 KB Correct.
6 Correct 357 ms 5476 KB Correct.
7 Correct 380 ms 4584 KB Correct.
8 Correct 192 ms 792 KB Correct.
9 Correct 153 ms 804 KB Correct.
10 Correct 152 ms 592 KB Correct.
11 Correct 132 ms 760 KB Correct.
12 Correct 171 ms 584 KB Correct.
13 Correct 169 ms 616 KB Correct.
14 Correct 852 ms 6188 KB Correct.
15 Correct 672 ms 5792 KB Correct.
16 Correct 317 ms 2308 KB Correct.
17 Correct 220 ms 856 KB Correct.
18 Correct 164 ms 592 KB Correct.
19 Correct 201 ms 592 KB Correct.
20 Correct 189 ms 592 KB Correct.
21 Correct 570 ms 348 KB Correct.
22 Correct 9 ms 344 KB Correct.
23 Correct 13 ms 344 KB Correct.
24 Correct 31 ms 860 KB Correct.