Submission #1065423

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1065423	2024-08-19T07:28:12 Z	stdfloat	Cyberland (APIO23_cyberland)	C++17	100 / 100	268 ms	10824 KB

cyberland

#include <bits/stdc++.h>
#include "cyberland.h"
// #include "stub.cpp"
using namespace std;
 
#define ff  first
#define ss  second
#define pii pair<int, int>
 
double solve(int n, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> a) {
    vector<pii> E[n];
    for (int i = 0; i < M; i++) {
        E[X[i]].push_back({Y[i], C[i]});
        E[Y[i]].push_back({X[i], C[i]});
    }
 
    queue<int> q;
    vector<bool> vis0(n);
    q.push(0); vis0[0] = true;
    while (!q.empty()) {
        int x = q.front(); q.pop();
 
        if (x == H) continue;
 
        for (auto [i, w] : E[x]) {
            if (!vis0[i]) {
                q.push(i);
                vis0[i] = true;
            }
        }
    }
 
    if (!vis0[H]) return -1;
 
    K = min(K, 66);
 
    vector<double> dis(n, 1e18);
    priority_queue<pair<double, int>> pq;
    for (int i = 0; i < n; i++) {
        if (!i || (!a[i] && vis0[i])) {
            dis[i] = 0;
            pq.push({0, i});
        }
    }
    for (int ii = 0; ii <= K; ii++) {
        vector<double> ndis = dis;
        priority_queue<pair<double, int>> npq;
        while (!pq.empty()) {
            auto [d, x] = pq.top(); d = -d; pq.pop();
        
            if (d != dis[x] || x == H) continue;
        
            for (auto [i, w] : E[x]) {
                if (!a[i]) continue;
    
                if (d + w < dis[i]) {
                    dis[i] = d + w;
                    pq.push({-dis[i], i});
                }
                if (a[i] == 2 && ii < K && (d + w) / 2 < ndis[i]) {
                    ndis[i] = (d + w) / 2;
                    npq.push({-ndis[i], i});
                }
            }
        }

        pq = npq;
        for (int i = 0; i < n; i++) {
            dis[i] = min(dis[i], ndis[i]);
        }
    }

    return dis[H];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	604 KB	Correct.
2	Correct	20 ms	592 KB	Correct.
3	Correct	19 ms	600 KB	Correct.
4	Correct	26 ms	348 KB	Correct.
5	Correct	22 ms	600 KB	Correct.
6	Correct	18 ms	1548 KB	Correct.
7	Correct	23 ms	1348 KB	Correct.
8	Correct	10 ms	2652 KB	Correct.
9	Correct	23 ms	524 KB	Correct.
10	Correct	18 ms	348 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	600 KB	Correct.
2	Correct	22 ms	604 KB	Correct.
3	Correct	21 ms	604 KB	Correct.
4	Correct	27 ms	348 KB	Correct.
5	Correct	20 ms	348 KB	Correct.
6	Correct	5 ms	1368 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	6492 KB	Correct.
2	Correct	27 ms	596 KB	Correct.
3	Correct	24 ms	604 KB	Correct.
4	Correct	35 ms	600 KB	Correct.
5	Correct	22 ms	512 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	604 KB	Correct.
2	Correct	23 ms	572 KB	Correct.
3	Correct	18 ms	600 KB	Correct.
4	Correct	18 ms	1568 KB	Correct.
5	Correct	15 ms	344 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	600 KB	Correct.
2	Correct	19 ms	572 KB	Correct.
3	Correct	31 ms	7256 KB	Correct.
4	Correct	15 ms	1116 KB	Correct.
5	Correct	17 ms	348 KB	Correct.
6	Correct	18 ms	600 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	604 KB	Correct.
2	Correct	4 ms	600 KB	Correct.
3	Correct	143 ms	10824 KB	Correct.
4	Correct	115 ms	2660 KB	Correct.
5	Correct	86 ms	7404 KB	Correct.
6	Correct	40 ms	5328 KB	Correct.
7	Correct	101 ms	2976 KB	Correct.
8	Correct	82 ms	848 KB	Correct.
9	Correct	25 ms	604 KB	Correct.
10	Correct	23 ms	604 KB	Correct.
11	Correct	76 ms	692 KB	Correct.
12	Correct	25 ms	600 KB	Correct.
13	Correct	25 ms	552 KB	Correct.
14	Correct	102 ms	5460 KB	Correct.
15	Correct	94 ms	1772 KB	Correct.
16	Correct	26 ms	600 KB	Correct.
17	Correct	27 ms	600 KB	Correct.
18	Correct	34 ms	604 KB	Correct.
19	Correct	55 ms	348 KB	Correct.
20	Correct	3 ms	344 KB	Correct.
21	Correct	2 ms	348 KB	Correct.
22	Correct	4 ms	860 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	604 KB	Correct.
2	Correct	5 ms	604 KB	Correct.
3	Correct	99 ms	10456 KB	Correct.
4	Correct	114 ms	1108 KB	Correct.
5	Correct	109 ms	7544 KB	Correct.
6	Correct	52 ms	5336 KB	Correct.
7	Correct	134 ms	4504 KB	Correct.
8	Correct	81 ms	752 KB	Correct.
9	Correct	27 ms	604 KB	Correct.
10	Correct	25 ms	604 KB	Correct.
11	Correct	102 ms	752 KB	Correct.
12	Correct	28 ms	1628 KB	Correct.
13	Correct	28 ms	1628 KB	Correct.
14	Correct	238 ms	7564 KB	Correct.
15	Correct	268 ms	7828 KB	Correct.
16	Correct	166 ms	4060 KB	Correct.
17	Correct	97 ms	2716 KB	Correct.
18	Correct	27 ms	1620 KB	Correct.
19	Correct	34 ms	1620 KB	Correct.
20	Correct	33 ms	1620 KB	Correct.
21	Correct	68 ms	2388 KB	Correct.
22	Correct	3 ms	348 KB	Correct.
23	Correct	3 ms	604 KB	Correct.
24	Correct	5 ms	1116 KB	Correct.

Submission #1065423

Compilation message