Submission #1065336

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1065336	2024-08-19T06:25:05 Z	stdfloat	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	91248 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]) 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], 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	604 KB	Correct.
2	Correct	24 ms	604 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	832 KB	Correct.
2	Correct	21 ms	860 KB	Correct.
3	Correct	20 ms	860 KB	Correct.
4	Correct	21 ms	840 KB	Correct.
5	Correct	21 ms	828 KB	Correct.
6	Correct	31 ms	3916 KB	Correct.
7	Correct	32 ms	3932 KB	Correct.
8	Correct	12 ms	7516 KB	Correct.
9	Correct	21 ms	532 KB	Correct.
10	Correct	19 ms	528 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	604 KB	Correct.
2	Correct	22 ms	764 KB	Correct.
3	Correct	20 ms	884 KB	Correct.
4	Correct	25 ms	516 KB	Correct.
5	Correct	21 ms	532 KB	Correct.
6	Correct	5 ms	3476 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	157 ms	23596 KB	Correct.
2	Correct	190 ms	988 KB	Correct.
3	Correct	160 ms	1056 KB	Correct.
4	Correct	179 ms	1008 KB	Correct.
5	Correct	153 ms	552 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	796 KB	Correct.
2	Correct	19 ms	760 KB	Correct.
3	Correct	21 ms	808 KB	Correct.
4	Correct	20 ms	3744 KB	Correct.
5	Correct	17 ms	536 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	860 KB	Correct.
2	Correct	18 ms	732 KB	Correct.
3	Correct	33 ms	7300 KB	Correct.
4	Correct	15 ms	2656 KB	Correct.
5	Correct	19 ms	532 KB	Correct.
6	Correct	25 ms	808 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	1156 KB	Correct.
2	Correct	27 ms	1692 KB	Correct.
3	Correct	627 ms	28376 KB	Correct.
4	Correct	458 ms	7644 KB	Correct.
5	Correct	637 ms	48448 KB	Correct.
6	Correct	324 ms	23812 KB	Correct.
7	Correct	438 ms	7460 KB	Correct.
8	Correct	447 ms	1668 KB	Correct.
9	Correct	147 ms	1380 KB	Correct.
10	Correct	140 ms	1348 KB	Correct.
11	Correct	440 ms	960 KB	Correct.
12	Correct	158 ms	1568 KB	Correct.
13	Correct	177 ms	1688 KB	Correct.
14	Correct	371 ms	9496 KB	Correct.
15	Correct	440 ms	3312 KB	Correct.
16	Correct	145 ms	1432 KB	Correct.
17	Correct	183 ms	1172 KB	Correct.
18	Correct	167 ms	1088 KB	Correct.
19	Correct	371 ms	1212 KB	Correct.
20	Correct	12 ms	600 KB	Correct.
21	Correct	11 ms	1056 KB	Correct.
22	Correct	28 ms	3284 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	575 ms	2648 KB	Correct.
2	Correct	77 ms	4468 KB	Correct.
3	Correct	490 ms	64596 KB	Correct.
4	Correct	971 ms	4692 KB	Correct.
5	Correct	2188 ms	91248 KB	Correct.
6	Correct	1131 ms	75968 KB	Correct.
7	Correct	1098 ms	23372 KB	Correct.
8	Correct	1110 ms	2084 KB	Correct.
9	Correct	509 ms	4692 KB	Correct.
10	Correct	482 ms	3968 KB	Correct.
11	Execution timed out	3025 ms	468 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Submission #1065336

Compilation message