Submission #1065283

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1065283	2024-08-19T05:52:07 Z	stdfloat	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	93052 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<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	860 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1624 KB	Correct.
2	Correct	22 ms	1880 KB	Correct.
3	Correct	22 ms	1628 KB	Correct.
4	Correct	22 ms	1628 KB	Correct.
5	Correct	22 ms	1872 KB	Correct.
6	Correct	22 ms	4944 KB	Correct.
7	Correct	27 ms	4604 KB	Correct.
8	Correct	13 ms	8164 KB	Correct.
9	Correct	21 ms	1368 KB	Correct.
10	Correct	20 ms	1420 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	1624 KB	Correct.
2	Correct	24 ms	1708 KB	Correct.
3	Correct	23 ms	1624 KB	Correct.
4	Correct	22 ms	1368 KB	Correct.
5	Correct	22 ms	1372 KB	Correct.
6	Correct	6 ms	3676 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	154 ms	24776 KB	Correct.
2	Correct	188 ms	1836 KB	Correct.
3	Correct	185 ms	1964 KB	Correct.
4	Correct	169 ms	1976 KB	Correct.
5	Correct	153 ms	1364 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	1632 KB	Correct.
2	Correct	21 ms	1884 KB	Correct.
3	Correct	19 ms	1764 KB	Correct.
4	Correct	20 ms	4444 KB	Correct.
5	Correct	16 ms	1144 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	1656 KB	Correct.
2	Correct	17 ms	1688 KB	Correct.
3	Correct	28 ms	9068 KB	Correct.
4	Correct	14 ms	3268 KB	Correct.
5	Correct	18 ms	1276 KB	Correct.
6	Correct	21 ms	1704 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	2064 KB	Correct.
2	Correct	26 ms	1704 KB	Correct.
3	Correct	599 ms	30364 KB	Correct.
4	Correct	481 ms	9912 KB	Correct.
5	Correct	672 ms	50148 KB	Correct.
6	Correct	334 ms	25280 KB	Correct.
7	Correct	455 ms	8632 KB	Correct.
8	Correct	449 ms	3200 KB	Correct.
9	Correct	149 ms	2076 KB	Correct.
10	Correct	141 ms	2372 KB	Correct.
11	Correct	440 ms	2796 KB	Correct.
12	Correct	161 ms	2276 KB	Correct.
13	Correct	180 ms	2424 KB	Correct.
14	Correct	384 ms	11028 KB	Correct.
15	Correct	445 ms	5360 KB	Correct.
16	Correct	149 ms	2296 KB	Correct.
17	Correct	195 ms	2104 KB	Correct.
18	Correct	172 ms	2112 KB	Correct.
19	Correct	381 ms	3196 KB	Correct.
20	Correct	13 ms	604 KB	Correct.
21	Correct	11 ms	900 KB	Correct.
22	Correct	26 ms	3284 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	551 ms	3832 KB	Correct.
2	Correct	77 ms	4672 KB	Correct.
3	Correct	497 ms	67024 KB	Correct.
4	Correct	976 ms	6348 KB	Correct.
5	Correct	2290 ms	93052 KB	Correct.
6	Correct	1195 ms	77612 KB	Correct.
7	Correct	1092 ms	25428 KB	Correct.
8	Correct	1129 ms	3884 KB	Correct.
9	Correct	506 ms	4960 KB	Correct.
10	Correct	498 ms	4908 KB	Correct.
11	Execution timed out	3049 ms	1456 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Submission #1065283

Compilation message