Submission #1142846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142846		vladilius	Cyberland (APIO23_cyberland)	C++20	97 / 100	3095 ms	91112 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define node tuple<double, int, int>
const double inf = 1e15;

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
    vector<pii> g[n + 1];
    for (int i = 0; i < m; i++){
        x[i]++; y[i]++;
        g[x[i]].pb({y[i], c[i]});
        g[y[i]].pb({x[i], c[i]});
    }

    k = min(k, 69); // LOL 
    arr.insert(arr.begin(), 0); h++;

    vector<bool> used(n + 1); used[1] = 1;
    queue<int> q; q.push(1);
    while (!q.empty()){
        int v = q.front(); q.pop();
        if (v == h) continue;
        for (auto [u, w]: g[v]){
            if (!used[u]){
                used[u] = 1;
                q.push(u);
            }
        }
    }
    
    double dp[n + 1][k + 1];
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= k; j++){
            dp[i][j] = inf;
        }
    }
    priority_queue<node, vector<node>, greater<node>> pq;
    dp[1][0] = 0; pq.push({0, 1, 0});
    for (int i = 1; i <= n; i++){
        if (used[i] && !arr[i]){
            for (int j = 0; j <= k; j++){
                dp[i][j] = 0;
            }
            pq.push({0, i, 0});
        }
    }
    while (!pq.empty()){
        node f = pq.top(); pq.pop();
        auto [d, v, x] = f;
        if (v == h) continue;
        for (auto [u, w]: g[v]){
            if (arr[u] == 1){
                double dist = d + w;
                if (dist < dp[u][x]){
                    dp[u][x] = dist;
                    pq.push({dist, u, x});
                }
            }
            else if (arr[u] == 2){
                double dist = d + w;
                if (dist < dp[u][x]){
                    dp[u][x] = dist;
                    pq.push({dist, u, x});
                }
                dist /= 2;
                if (x < k && dist < dp[u][x + 1]){
                    dp[u][x + 1] = dist;
                    pq.push({dist, u, x + 1});
                }
            }
        }
    }

    double out = inf;
    for (int i = 0; i <= k; i++){
        out = min(out, dp[h][i]);
    }

    return (out == inf) ? -1 : out;
}

• 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: 0 / 3