Submission #1065281

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1065281	2024-08-19T05:50:55 Z	stdfloat	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	92796 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, 68);
 
    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	860 KB	Correct.
2	Correct	15 ms	884 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	1368 KB	Correct.
2	Correct	22 ms	1624 KB	Correct.
3	Correct	42 ms	1372 KB	Correct.
4	Correct	22 ms	1628 KB	Correct.
5	Correct	22 ms	1468 KB	Correct.
6	Correct	27 ms	4676 KB	Correct.
7	Correct	34 ms	4352 KB	Correct.
8	Correct	15 ms	8020 KB	Correct.
9	Correct	24 ms	1016 KB	Correct.
10	Correct	21 ms	968 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	1568 KB	Correct.
2	Correct	25 ms	1512 KB	Correct.
3	Correct	22 ms	1372 KB	Correct.
4	Correct	23 ms	1016 KB	Correct.
5	Correct	22 ms	1104 KB	Correct.
6	Correct	6 ms	3676 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	24620 KB	Correct.
2	Correct	190 ms	1548 KB	Correct.
3	Correct	165 ms	1652 KB	Correct.
4	Correct	170 ms	1720 KB	Correct.
5	Correct	158 ms	1108 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	1392 KB	Correct.
2	Correct	34 ms	1628 KB	Correct.
3	Correct	21 ms	1532 KB	Correct.
4	Correct	30 ms	4096 KB	Correct.
5	Correct	16 ms	1024 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	1540 KB	Correct.
2	Correct	18 ms	1304 KB	Correct.
3	Correct	29 ms	8456 KB	Correct.
4	Correct	22 ms	3192 KB	Correct.
5	Correct	19 ms	960 KB	Correct.
6	Correct	21 ms	1488 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	172 ms	1820 KB	Correct.
2	Correct	25 ms	1704 KB	Correct.
3	Correct	692 ms	30044 KB	Correct.
4	Correct	471 ms	9268 KB	Correct.
5	Correct	723 ms	49680 KB	Correct.
6	Correct	350 ms	25016 KB	Correct.
7	Correct	455 ms	8296 KB	Correct.
8	Correct	470 ms	2676 KB	Correct.
9	Correct	156 ms	1756 KB	Correct.
10	Correct	158 ms	2000 KB	Correct.
11	Correct	462 ms	2080 KB	Correct.
12	Correct	165 ms	2068 KB	Correct.
13	Correct	181 ms	2020 KB	Correct.
14	Correct	401 ms	10488 KB	Correct.
15	Correct	467 ms	4548 KB	Correct.
16	Correct	159 ms	1932 KB	Correct.
17	Correct	190 ms	1900 KB	Correct.
18	Correct	174 ms	1816 KB	Correct.
19	Correct	383 ms	2472 KB	Correct.
20	Correct	12 ms	600 KB	Correct.
21	Correct	11 ms	892 KB	Correct.
22	Correct	27 ms	3284 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	602 ms	3436 KB	Correct.
2	Correct	82 ms	4596 KB	Correct.
3	Correct	571 ms	67768 KB	Correct.
4	Correct	1030 ms	5620 KB	Correct.
5	Correct	2473 ms	92796 KB	Correct.
6	Correct	1335 ms	77264 KB	Correct.
7	Correct	1165 ms	25128 KB	Correct.
8	Correct	1198 ms	3224 KB	Correct.
9	Correct	535 ms	4568 KB	Correct.
10	Correct	560 ms	4628 KB	Correct.
11	Execution timed out	3068 ms	1444 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Submission #1065281

Compilation message