Submission #1065332

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1065332	2024-08-19T06:23:17 Z	stdfloat	Cyberland (APIO23_cyberland)	C++17	97 / 100	3000 ms	93164 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()) {
        double d = pq.top().ff; d = -d;
        int x = pq.top().ss; 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	14 ms	604 KB	Correct.
2	Correct	18 ms	604 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	860 KB	Correct.
2	Correct	21 ms	860 KB	Correct.
3	Correct	20 ms	860 KB	Correct.
4	Correct	21 ms	600 KB	Correct.
5	Correct	21 ms	824 KB	Correct.
6	Correct	20 ms	4036 KB	Correct.
7	Correct	26 ms	3796 KB	Correct.
8	Correct	14 ms	7512 KB	Correct.
9	Correct	19 ms	348 KB	Correct.
10	Correct	18 ms	524 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	824 KB	Correct.
2	Correct	22 ms	764 KB	Correct.
3	Correct	20 ms	880 KB	Correct.
4	Correct	21 ms	348 KB	Correct.
5	Correct	20 ms	348 KB	Correct.
6	Correct	5 ms	3420 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	23496 KB	Correct.
2	Correct	185 ms	972 KB	Correct.
3	Correct	179 ms	1024 KB	Correct.
4	Correct	167 ms	960 KB	Correct.
5	Correct	147 ms	548 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	796 KB	Correct.
2	Correct	21 ms	752 KB	Correct.
3	Correct	24 ms	808 KB	Correct.
4	Correct	19 ms	3676 KB	Correct.
5	Correct	15 ms	508 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	848 KB	Correct.
2	Correct	16 ms	728 KB	Correct.
3	Correct	26 ms	7248 KB	Correct.
4	Correct	13 ms	2756 KB	Correct.
5	Correct	17 ms	348 KB	Correct.
6	Correct	18 ms	800 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	1140 KB	Correct.
2	Correct	25 ms	1704 KB	Correct.
3	Correct	593 ms	28236 KB	Correct.
4	Correct	472 ms	7640 KB	Correct.
5	Correct	705 ms	48544 KB	Correct.
6	Correct	361 ms	23788 KB	Correct.
7	Correct	462 ms	7456 KB	Correct.
8	Correct	455 ms	1820 KB	Correct.
9	Correct	161 ms	1376 KB	Correct.
10	Correct	145 ms	1472 KB	Correct.
11	Correct	439 ms	976 KB	Correct.
12	Correct	160 ms	1404 KB	Correct.
13	Correct	177 ms	1512 KB	Correct.
14	Correct	392 ms	9416 KB	Correct.
15	Correct	471 ms	3312 KB	Correct.
16	Correct	153 ms	1376 KB	Correct.
17	Correct	189 ms	1324 KB	Correct.
18	Correct	181 ms	1204 KB	Correct.
19	Correct	384 ms	1216 KB	Correct.
20	Correct	14 ms	600 KB	Correct.
21	Correct	12 ms	1048 KB	Correct.
22	Correct	27 ms	3284 KB	Correct.

Subtask #8
0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	549 ms	2840 KB	Correct.
2	Correct	82 ms	4548 KB	Correct.
3	Correct	521 ms	64592 KB	Correct.
4	Correct	1004 ms	6436 KB	Correct.
5	Correct	2366 ms	93164 KB	Correct.
6	Correct	1224 ms	77436 KB	Correct.
7	Correct	1079 ms	25420 KB	Correct.
8	Correct	1119 ms	4000 KB	Correct.
9	Correct	506 ms	5176 KB	Correct.
10	Correct	495 ms	4908 KB	Correct.
11	Execution timed out	3020 ms	1528 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Submission #1065332

Compilation message