Submission #1065390

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1065390	2024-08-19T06:54:57 Z	stdfloat	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	94660 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, int>> pq;
    for (int i = 0; i < n; i++) {
        if (!i || (!a[i] && vis0[i])) {
            dis[i][0] = 0;
            pq.push({0, 70 * i});
        }
    }
    while (!pq.empty()) {
        auto [d, x] = pq.top(); d = -d; pq.pop();
        int y = x % 70; x /= 70;
    
        if (d != dis[x][y] || 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], y + 70 * i});
            }
            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], y + 1 + 70 * i});
            }
        }
    }
 
    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	17 ms	860 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	1628 KB	Correct.
2	Correct	22 ms	1808 KB	Correct.
3	Correct	21 ms	1624 KB	Correct.
4	Correct	21 ms	1628 KB	Correct.
5	Correct	22 ms	1696 KB	Correct.
6	Correct	20 ms	4940 KB	Correct.
7	Correct	28 ms	4700 KB	Correct.
8	Correct	15 ms	8028 KB	Correct.
9	Correct	20 ms	1372 KB	Correct.
10	Correct	19 ms	1292 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	1624 KB	Correct.
2	Correct	24 ms	1708 KB	Correct.
3	Correct	23 ms	1628 KB	Correct.
4	Correct	21 ms	1280 KB	Correct.
5	Correct	23 ms	1360 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	24940 KB	Correct.
2	Correct	187 ms	1868 KB	Correct.
3	Correct	157 ms	1944 KB	Correct.
4	Correct	170 ms	2068 KB	Correct.
5	Correct	146 ms	1460 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	1628 KB	Correct.
2	Correct	22 ms	1756 KB	Correct.
3	Correct	19 ms	1764 KB	Correct.
4	Correct	22 ms	4392 KB	Correct.
5	Correct	17 ms	1116 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	1880 KB	Correct.
2	Correct	17 ms	1688 KB	Correct.
3	Correct	28 ms	9044 KB	Correct.
4	Correct	13 ms	3264 KB	Correct.
5	Correct	18 ms	1368 KB	Correct.
6	Correct	18 ms	1696 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	167 ms	2076 KB	Correct.
2	Correct	25 ms	1852 KB	Correct.
3	Correct	542 ms	30700 KB	Correct.
4	Correct	471 ms	9996 KB	Correct.
5	Correct	600 ms	51104 KB	Correct.
6	Correct	305 ms	27184 KB	Correct.
7	Correct	437 ms	7544 KB	Correct.
8	Correct	439 ms	3188 KB	Correct.
9	Correct	155 ms	1420 KB	Correct.
10	Correct	143 ms	2404 KB	Correct.
11	Correct	438 ms	2700 KB	Correct.
12	Correct	162 ms	2272 KB	Correct.
13	Correct	175 ms	2412 KB	Correct.
14	Correct	377 ms	11036 KB	Correct.
15	Correct	437 ms	5360 KB	Correct.
16	Correct	149 ms	2200 KB	Correct.
17	Correct	183 ms	2196 KB	Correct.
18	Correct	169 ms	2128 KB	Correct.
19	Correct	375 ms	3164 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	539 ms	3604 KB	Correct.
2	Correct	77 ms	4676 KB	Correct.
3	Correct	481 ms	67184 KB	Correct.
4	Correct	951 ms	6280 KB	Correct.
5	Correct	2081 ms	94660 KB	Correct.
6	Correct	1107 ms	77220 KB	Correct.
7	Correct	1058 ms	26116 KB	Correct.
8	Correct	1112 ms	3104 KB	Correct.
9	Correct	498 ms	5032 KB	Correct.
10	Correct	508 ms	4776 KB	Correct.
11	Execution timed out	3023 ms	1364 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Submission #1065390

Compilation message