Submission #836740

#	Time	Username	Problem	Language	Result	Execution time	Memory
836740		SoulKnight	Cyberland (APIO23_cyberland)	C++17	97 / 100	570 ms	51212 KiB

cyberland

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

using namespace std;

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

const int N = 1e5 + 5;
const int LG = 52;
const double INF = 1e16;

vector<array<ll, 2>> adj[N];
double dist[N][LG], p2[LG];
priority_queue<array<double, 3>, vector<array<double, 3>>, greater<array<double, 3>>> pq;
set<int> node;
queue<int> q;
bool seen[N];

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(); seen[i] = 0;}
    node.clear();
    K = min(K, 50);
    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++){
        adj[x[i]].push_back({c[i], y[i]});
        adj[y[i]].push_back({c[i], x[i]});
    }

    q.push(0); seen[0] = 1;
    while (!q.empty()){
        int cur = q.front(); q.pop();
        if (cur == H) continue;
        for (auto& [e, v]: adj[cur]){
            if (seen[v]) continue;
            seen[v] = 1;
            if (arr[v] == 0) node.insert(v);
            q.push(v);
        }
    }

    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)

    double ans = INF;

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

        // cout << w << ' ' << u << ' ' << cnt << ln;
        // cout << (w > dist[u][cnt]) << ln;
        if (w > dist[u][cnt]) continue;
        if (arr[u] == 0 && node.count(u)) {ans = min(ans, w); continue;}
        // cout << "what" << ln;
        for (auto& [e, v]: adj[u]){
            // cout << v << ' ' << dist[v][cnt] << ln;
            if (dist[v][cnt] >= INF || w + e / p2[cnt] < dist[v][cnt]){
                dist[v][cnt] = w + e / p2[cnt];
                pq.push({dist[v][cnt], v, min(K, cnt + (arr[v] == 2))});
            }
        }
    }


    for (int j = 0; j <= K; j++){
        ans = min(ans, dist[0][j]);
        // cout << dist[0][j] << " ";
    }
    ans = ((ans >= INF)? -1: ans);
    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:55:19: warning: narrowing conversion of 'H' from 'int' to 'double' [-Wnarrowing]
   55 |     pq.push({0.0, H, 0}); // (w, node, # of /2)
      |                   ^
cyberland.cpp:74:40: warning: narrowing conversion of 'v' from 'std::tuple_element<1, std::array<long long int, 2> >::type' {aka 'long long int'} to 'double' [-Wnarrowing]
   74 |                 pq.push({dist[v][cnt], v, min(K, cnt + (arr[v] == 2))});
      |                                        ^
cyberland.cpp:74: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 'double' [-Wnarrowing]
   74 |                 pq.push({dist[v][cnt], v, min(K, cnt + (arr[v] == 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: 0 / 3