Submission #920300

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
920300	2024-02-02T12:28:13 Z	vjudge1	Cyberland (APIO23_cyberland)	C++17	100 / 100	868 ms	12156 KB

cyberland

#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	344 KB	Correct.
2	Correct	22 ms	344 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	600 KB	Correct.
2	Correct	22 ms	556 KB	Correct.
3	Correct	23 ms	604 KB	Correct.
4	Correct	22 ms	600 KB	Correct.
5	Correct	22 ms	600 KB	Correct.
6	Correct	19 ms	1436 KB	Correct.
7	Correct	23 ms	1404 KB	Correct.
8	Correct	10 ms	2632 KB	Correct.
9	Correct	21 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	23 ms	344 KB	Correct.
2	Correct	22 ms	572 KB	Correct.
3	Correct	21 ms	600 KB	Correct.
4	Correct	24 ms	344 KB	Correct.
5	Correct	23 ms	344 KB	Correct.
6	Correct	5 ms	1116 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	6760 KB	Correct.
2	Correct	78 ms	596 KB	Correct.
3	Correct	68 ms	592 KB	Correct.
4	Correct	73 ms	572 KB	Correct.
5	Correct	50 ms	344 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	600 KB	Correct.
2	Correct	22 ms	348 KB	Correct.
3	Correct	22 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	21 ms	604 KB	Correct.
2	Correct	19 ms	600 KB	Correct.
3	Correct	33 ms	8536 KB	Correct.
4	Correct	13 ms	1204 KB	Correct.
5	Correct	22 ms	344 KB	Correct.
6	Correct	22 ms	600 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	596 KB	Correct.
2	Correct	15 ms	600 KB	Correct.
3	Correct	279 ms	10824 KB	Correct.
4	Correct	203 ms	2564 KB	Correct.
5	Correct	324 ms	7824 KB	Correct.
6	Correct	150 ms	5448 KB	Correct.
7	Correct	198 ms	2764 KB	Correct.
8	Correct	157 ms	672 KB	Correct.
9	Correct	75 ms	592 KB	Correct.
10	Correct	74 ms	600 KB	Correct.
11	Correct	142 ms	600 KB	Correct.
12	Correct	83 ms	592 KB	Correct.
13	Correct	82 ms	612 KB	Correct.
14	Correct	189 ms	5576 KB	Correct.
15	Correct	180 ms	1636 KB	Correct.
16	Correct	80 ms	592 KB	Correct.
17	Correct	96 ms	600 KB	Correct.
18	Correct	94 ms	592 KB	Correct.
19	Correct	246 ms	344 KB	Correct.
20	Correct	5 ms	344 KB	Correct.
21	Correct	6 ms	344 KB	Correct.
22	Correct	12 ms	856 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	194 ms	848 KB	Correct.
2	Correct	33 ms	600 KB	Correct.
3	Correct	110 ms	12156 KB	Correct.
4	Correct	232 ms	2176 KB	Correct.
5	Correct	795 ms	8140 KB	Correct.
6	Correct	352 ms	6968 KB	Correct.
7	Correct	380 ms	6636 KB	Correct.
8	Correct	197 ms	2688 KB	Correct.
9	Correct	152 ms	1360 KB	Correct.
10	Correct	150 ms	1360 KB	Correct.
11	Correct	127 ms	1616 KB	Correct.
12	Correct	172 ms	1580 KB	Correct.
13	Correct	175 ms	1828 KB	Correct.
14	Correct	868 ms	7716 KB	Correct.
15	Correct	666 ms	7904 KB	Correct.
16	Correct	323 ms	4112 KB	Correct.
17	Correct	222 ms	2640 KB	Correct.
18	Correct	165 ms	1616 KB	Correct.
19	Correct	199 ms	1456 KB	Correct.
20	Correct	188 ms	1428 KB	Correct.
21	Correct	560 ms	2468 KB	Correct.
22	Correct	10 ms	344 KB	Correct.
23	Correct	13 ms	592 KB	Correct.
24	Correct	27 ms	1112 KB	Correct.

Submission #920300

Compilation message