Submission #1065280

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1065280	2024-08-19T05:50:06 Z	stdfloat	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	92532 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, 70);
 
    vector<vector<double>> dis(n, vector<double>(K + 1, 1e18));
    priority_queue<pair<double, pii>> pq;
    for (int i = 0; i < n; i++) {
        if (!i || (!a[i] && vis0[i])) {
            dis[i][0] = 0;
            pq.push({0, {i, 0}});
        }
    }
    while (!pq.empty()) {
        double d = pq.top().ff; d = -d;
        auto [x, y] = pq.top().ss; pq.pop();
    
        if (d != dis[x][y]) continue;
 
        if (x == H) continue;
    
        for (auto [i, w] : E[x]) {
            if (!a[i]) continue;
 
            if (d + w < dis[i][y]) {
                dis[i][y] = d + w;
                pq.push({-dis[i][y], {i, y}});
            }
            if (a[i] == 2 && y < K && (d + w) / 2 < dis[i][y + 1]) {
                dis[i][y + 1] = (d + w) / 2;
                pq.push({-dis[i][y + 1], {i, y + 1}});
            }
        }
    }
 
    return *min_element(dis[H].begin(), dis[H].end());
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	1628 KB	Correct.
2	Correct	24 ms	1576 KB	Correct.
3	Correct	22 ms	1628 KB	Correct.
4	Correct	22 ms	1372 KB	Correct.
5	Correct	31 ms	1628 KB	Correct.
6	Correct	21 ms	4680 KB	Correct.
7	Correct	26 ms	4700 KB	Correct.
8	Correct	13 ms	8024 KB	Correct.
9	Correct	20 ms	1112 KB	Correct.
10	Correct	20 ms	1116 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	1372 KB	Correct.
2	Correct	22 ms	1452 KB	Correct.
3	Correct	22 ms	1624 KB	Correct.
4	Correct	21 ms	1116 KB	Correct.
5	Correct	27 ms	1288 KB	Correct.
6	Correct	6 ms	3676 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	153 ms	24576 KB	Correct.
2	Correct	190 ms	1644 KB	Correct.
3	Correct	161 ms	1780 KB	Correct.
4	Correct	169 ms	1728 KB	Correct.
5	Correct	168 ms	1108 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	1504 KB	Correct.
2	Correct	21 ms	1368 KB	Correct.
3	Correct	24 ms	1536 KB	Correct.
4	Correct	20 ms	4440 KB	Correct.
5	Correct	16 ms	1112 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1628 KB	Correct.
2	Correct	17 ms	1500 KB	Correct.
3	Correct	28 ms	8668 KB	Correct.
4	Correct	14 ms	3268 KB	Correct.
5	Correct	19 ms	1280 KB	Correct.
6	Correct	19 ms	1556 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	1876 KB	Correct.
2	Correct	25 ms	1692 KB	Correct.
3	Correct	587 ms	29884 KB	Correct.
4	Correct	455 ms	8936 KB	Correct.
5	Correct	658 ms	49416 KB	Correct.
6	Correct	326 ms	24872 KB	Correct.
7	Correct	446 ms	8548 KB	Correct.
8	Correct	451 ms	3096 KB	Correct.
9	Correct	148 ms	2136 KB	Correct.
10	Correct	141 ms	2272 KB	Correct.
11	Correct	434 ms	2248 KB	Correct.
12	Correct	165 ms	2184 KB	Correct.
13	Correct	179 ms	2164 KB	Correct.
14	Correct	376 ms	10780 KB	Correct.
15	Correct	446 ms	4596 KB	Correct.
16	Correct	146 ms	2196 KB	Correct.
17	Correct	183 ms	1976 KB	Correct.
18	Correct	169 ms	1880 KB	Correct.
19	Correct	373 ms	2540 KB	Correct.
20	Correct	12 ms	604 KB	Correct.
21	Correct	11 ms	1048 KB	Correct.
22	Correct	25 ms	3284 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	589 ms	4656 KB	Correct.
2	Correct	86 ms	4860 KB	Correct.
3	Correct	526 ms	67792 KB	Correct.
4	Correct	1047 ms	5008 KB	Correct.
5	Correct	2411 ms	92532 KB	Correct.
6	Correct	1262 ms	77940 KB	Correct.
7	Correct	1144 ms	26760 KB	Correct.
8	Correct	1216 ms	4044 KB	Correct.
9	Correct	553 ms	5540 KB	Correct.
10	Correct	526 ms	4920 KB	Correct.
11	Execution timed out	3030 ms	1536 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Submission #1065280

Compilation message