Submission #765388

#	Time	Username	Problem	Language	Result	Execution time	Memory
765388		pandapythoner	Cyberland (APIO23_cyberland)	C++17	100 / 100	2548 ms	20076 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;

#define flt long double

struct edge {
    int to;
    long long cost;
};

const flt inf = 1e100;
int n, m;
vector<vector<edge>> g;

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) {
    n = N;
    m = M;
    K = min(K, 70);
    g.assign(n, {});
    for (int i = 0; i < m; i += 1) {
        int u = x[i];
        int v = y[i];
        int cost = c[i];
        g[u].push_back({v, cost});
        g[v].push_back({u, cost});
    }
    vector<flt> dst(n, inf);
    dst[0] = 0;
    for(int iter = 0; iter <= K + 2; iter += 1){
        set<pair<flt, int>> q;
        for(int i = 0; i < n; i += 1){
            q.emplace(dst[i], i);
        }
        while(!q.empty()){
            int v = q.begin()->second;
            q.erase(q.begin());
            if(v == H){
                continue;
            }
            for(auto [to, cost]: g[v]){
                if(dst[to] > dst[v] + cost){
                    q.erase(make_pair(dst[to], to));
                    dst[to] = dst[v] + cost;
                    q.insert(make_pair(dst[to], to));
                }
            }
        }
        auto new_dst = dst;
        for(int i = 0; i < n; i += 1){
            if(dst[i] < inf / 10){
                if(arr[i] == 0){
                    new_dst[i] = 0;
                } else if(arr[i] == 2 && iter > 1 && iter != K + 2){
                    for(auto [to, cost]: g[i]){
                        new_dst[to] = min(new_dst[to], dst[i] / 2 + (flt)(cost));
                    }
                }
            }
        }
        dst = new_dst;
    }
    if(dst[H] >= inf / 10){
        return -1;
    }
    return dst[H];
}

/*
3 2 30 2
*/

• 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