Submission #876389

#	Time	Username	Problem	Language	Result	Execution time	Memory
876389		hmm789	Cyberland (APIO23_cyberland)	C++17	15 / 100	693 ms	29120 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
 
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    K = min(K, 66);
    int cur, num;
    double d, ans = -1;
    vector<pair<int, int>> adj[N];
    for(int i = 0; i < M; i++) {
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }
    double dist[N][K+1];
    for(int i = 0; i < N; i++) for(int j = 0; j <= K; j++) dist[i][j] = -1;
    dist[0][0] = 0;
    priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> pq;
    pq.push({0, 0, 0});
    for(int i = 0; i < N; i++) if(arr[i] == 0) {
        dist[i][0] = 0;
        pq.push({0, i, 0});
    }
    while(!pq.empty()) {
        tie(d, cur, num) = pq.top();
        pq.pop();
        if(dist[cur][num] != d) continue;
        if(cur == H) continue;
        for(auto i : adj[cur]) {
            double nd = d+i.second;
            if(arr[i.first] == 0) nd = 0;
            if(dist[i.first][num] == -1 || dist[i.first][num] > nd) {
                dist[i.first][num] = nd;
                pq.push({nd, i.first, num});
            }
            if(arr[i.first] == 2) {
                if(num+1 > K) continue;
                nd /= 2.0;
                if(dist[i.first][num+1] == -1 || dist[i.first][num+1] > nd) {
                    dist[i.first][num+1] = nd;
                    pq.push({nd, i.first, num+1});
                }
            }
        }
    }
    for(int i = 0; i <= K; i++) {
        if(dist[H][i] != -1) {
            if(ans == -1) ans = dist[H][i];
            else ans = min(ans, dist[H][i]);
        }
    }
    return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3