Submission #836592

#	Time	Username	Problem	Language	Result	Execution time	Memory
836592		SoulKnight	Cyberland (APIO23_cyberland)	C++17	8 / 100	1018 ms	106220 KiB

cyberland

#include "cyberland.h"
// #include "bits/stdc++.h"
#include <vector>
#include <iostream>
#include <array>
#include <queue>
#include <numeric>

using namespace std;

#define ll long long
#define ln '\n'

const int N = 1e5 + 5;
const int LG = 50;
const long double INF = 5e18;

int par[N];
vector<array<ll, 2>> adj[N];
long double dist[N][LG], p2[LG];
priority_queue<array<long double, 3>, vector<array<long double, 3>>, greater<array<long double, 3>>> pq;

int find(int u){return (par[u]==u? u: par[u]=find(par[u]));}



double solve(int NN, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    for (int i = 0; i < NN; i++) adj[i].clear();
    iota(par, par+NN, 0);
    K = min(K, LG);
    p2[0] = 1.0;
    for (int i = 1; i < LG; i++) p2[i] = p2[i-1] * 2.0;

    for (int i = 0; i < M; i++){
        if (x[i] > y[i]) swap(x[i], y[i]);
        if (x[i] == 0 && arr[y[i]] == 0) {c[i] = 0; arr[y[i]] = 1;} // no multi-edge

        adj[x[i]].push_back({c[i], y[i]});
        adj[y[i]].push_back({c[i], x[i]});
        par[find(x[i])] = find(y[i]);
    }

    for (int i = 0; i < NN; i++){
        if (arr[i] != 0 || find(i) != find(0)) continue;
        adj[0].push_back({0, i});
        adj[i].push_back({0, 0});
    }

    for (int i = 0; i < NN; i++){
        for (int j = 0; j < LG; j++) dist[i][j] = INF;
    }
    for (int j = 0; j < LG; j++) dist[H][j] = 0.0;
    pq.push({0.0, H, 0}); // (w, node, # of /2)

    while (!pq.empty()){
        long double w = pq.top()[0];
        int u = pq.top()[1];
        int cnt = pq.top()[2];
        pq.pop();

        if (w > dist[u][cnt]) continue;

        for (auto& [e, v]: adj[u]){
            if (w * p2[cnt] + e < dist[v][cnt] * p2[cnt]){
                dist[v][cnt] = w + e / p2[cnt];
                pq.push({dist[v][cnt], v, min(K, cnt + (arr[v] == 2))});
            }
        }
    }

    long double ans = INF;
    for (int j = 0; j <= K; j++){
        ans = min(ans, dist[0][j]);
    }

    return ans;


}

Compilation message (stderr)

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:53:19: warning: narrowing conversion of 'H' from 'int' to 'long double' [-Wnarrowing]
   53 |     pq.push({0.0, H, 0}); // (w, node, # of /2)
      |                   ^
cyberland.cpp:66:40: warning: narrowing conversion of 'v' from 'std::tuple_element<1, std::array<long long int, 2> >::type' {aka 'long long int'} to 'long double' [-Wnarrowing]
   66 |                 pq.push({dist[v][cnt], v, min(K, cnt + (arr[v] == 2))});
      |                                        ^
cyberland.cpp:66:46: warning: narrowing conversion of '(int)std::min<int>(K, (cnt + (arr.std::vector<int>::operator[](((std::vector<int>::size_type)v)) == 2)))' from 'int' to 'long double' [-Wnarrowing]
   66 |                 pq.push({dist[v][cnt], v, min(K, cnt + (arr[v] == 2))});
      |                                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~

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