Submission #1025571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025571		saayan007	Cyberland (APIO23_cyberland)	C++17	100 / 100	1370 ms	70776 KiB

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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3