Submission #1025571

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1025571	2024-07-17T07:20:09 Z	saayan007	Cyberland (APIO23_cyberland)	C++17	100 / 100	1370 ms	70776 KB

cyberland

#include "cyberland.h"
#include "bits/stdc++.h"
using namespace std;
#define fr first
#define sc second

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    k = min(k, 70); 
    vector<pair<int, int>> adj[n];
    for(int i = 0; i < m; ++i) {
        adj[x[i]].emplace_back(y[i], c[i]);
        adj[y[i]].emplace_back(x[i], c[i]);
    }
    const double inf = 2e18;
    double dp[n][k + 1];
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j <= k; ++j) {
            dp[i][j] = inf;
        }
    }

    dp[0][0] = 0;
    for(int st = 0; st <= k; ++st) {
        priority_queue<pair<double, int>> pq;
        if(st > 0) {
            for(int i = 0; i < n; ++i) {
                dp[i][st] = min(dp[i][st], dp[i][st - 1]);
            }
        }
        for(int i = 0; i < n; ++i) if(dp[i][st] != inf) pq.emplace(-dp[i][st], i);
        while(!pq.empty()) {
            double cost = -pq.top().fr; int city = pq.top().sc;
            pq.pop();
            if(city == h || dp[city][st] < cost) continue;
            for(auto [dest, wt] : adj[city]) {
                if(arr[dest] == 0) {
                    if(dp[dest][st] > 0) {
                        dp[dest][st] = 0;
                        pq.emplace(-dp[dest][st], dest);
                    }
                }
                else {
                    if(dp[dest][st] > cost + wt) {
                        dp[dest][st] = cost + wt;
                        pq.emplace(-dp[dest][st], dest);
                    }
                    if(arr[dest] == 2 && st < k && dp[dest][st + 1] > (cost + wt) / 2) {
                        dp[dest][st + 1] = (cost + wt) / 2;
                    }
                }
            }
        }
    }

    return dp[h][k] == inf ? -1 : dp[h][k];
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	848 KB	Correct.
2	Correct	27 ms	828 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	1576 KB	Correct.
2	Correct	78 ms	1876 KB	Correct.
3	Correct	73 ms	1616 KB	Correct.
4	Correct	83 ms	1820 KB	Correct.
5	Correct	77 ms	1872 KB	Correct.
6	Correct	191 ms	5020 KB	Correct.
7	Correct	244 ms	4876 KB	Correct.
8	Correct	113 ms	8248 KB	Correct.
9	Correct	59 ms	1384 KB	Correct.
10	Correct	55 ms	1388 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	1664 KB	Correct.
2	Correct	89 ms	1616 KB	Correct.
3	Correct	82 ms	1616 KB	Correct.
4	Correct	64 ms	1360 KB	Correct.
5	Correct	64 ms	1360 KB	Correct.
6	Correct	41 ms	3544 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	110 ms	21456 KB	Correct.
2	Correct	75 ms	1872 KB	Correct.
3	Correct	63 ms	1616 KB	Correct.
4	Correct	73 ms	1616 KB	Correct.
5	Correct	45 ms	1372 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	1732 KB	Correct.
2	Correct	45 ms	1692 KB	Correct.
3	Correct	46 ms	1656 KB	Correct.
4	Correct	96 ms	4604 KB	Correct.
5	Correct	36 ms	1112 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	1836 KB	Correct.
2	Correct	41 ms	1684 KB	Correct.
3	Correct	48 ms	27472 KB	Correct.
4	Correct	64 ms	3656 KB	Correct.
5	Correct	42 ms	1368 KB	Correct.
6	Correct	47 ms	1616 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	1612 KB	Correct.
2	Correct	10 ms	1116 KB	Correct.
3	Correct	603 ms	28548 KB	Correct.
4	Correct	395 ms	9204 KB	Correct.
5	Correct	327 ms	18076 KB	Correct.
6	Correct	125 ms	9040 KB	Correct.
7	Correct	378 ms	8116 KB	Correct.
8	Correct	264 ms	3456 KB	Correct.
9	Correct	58 ms	1696 KB	Correct.
10	Correct	59 ms	2128 KB	Correct.
11	Correct	201 ms	2640 KB	Correct.
12	Correct	63 ms	1628 KB	Correct.
13	Correct	61 ms	1852 KB	Correct.
14	Correct	318 ms	10460 KB	Correct.
15	Correct	304 ms	4976 KB	Correct.
16	Correct	59 ms	1620 KB	Correct.
17	Correct	79 ms	1872 KB	Correct.
18	Correct	69 ms	1828 KB	Correct.
19	Correct	215 ms	2600 KB	Correct.
20	Correct	5 ms	344 KB	Correct.
21	Correct	5 ms	808 KB	Correct.
22	Correct	9 ms	1116 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	120 ms	2128 KB	Correct.
2	Correct	16 ms	1628 KB	Correct.
3	Correct	1143 ms	70776 KB	Correct.
4	Correct	405 ms	5460 KB	Correct.
5	Correct	683 ms	28976 KB	Correct.
6	Correct	261 ms	12272 KB	Correct.
7	Correct	540 ms	17292 KB	Correct.
8	Correct	267 ms	3412 KB	Correct.
9	Correct	89 ms	1876 KB	Correct.
10	Correct	94 ms	1872 KB	Correct.
11	Correct	169 ms	1700 KB	Correct.
12	Correct	108 ms	2132 KB	Correct.
13	Correct	99 ms	2112 KB	Correct.
14	Correct	1036 ms	29624 KB	Correct.
15	Correct	1370 ms	36368 KB	Correct.
16	Correct	624 ms	13372 KB	Correct.
17	Correct	343 ms	4688 KB	Correct.
18	Correct	97 ms	1976 KB	Correct.
19	Correct	117 ms	2120 KB	Correct.
20	Correct	113 ms	2132 KB	Correct.
21	Correct	358 ms	2900 KB	Correct.
22	Correct	8 ms	604 KB	Correct.
23	Correct	12 ms	1116 KB	Correct.
24	Correct	16 ms	1372 KB	Correct.

Submission #1025571

Compilation message