Submission #1160428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160428		lrnnz	사이버랜드 (APIO23_cyberland)	C++17	100 / 100	2903 ms	22692 KiB

cyberland

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <tuple>
using namespace std;
 
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back
#define ll long long
#define ld long double
#define ui uint64_t
#define ar array
#define us unordered_set
#define cont(set, element) ((set).find(element) != (set).end())
 
/********* DEBUG *********/
template <typename T>
void outvec(const vector<T>& Z, int hi = INT_MAX) {
    int count = 0;
    for (const T& x : Z) {
        if (count >= hi) break;
        cout << x << ' ';
        count++;
    }
    cout << "\n";
}

// overloaded function for raw arrays
template <typename T, size_t N>
void outvec(const T (&arr)[N], int hi = INT_MAX) {
    int count = 0;
    for (size_t i = 0; i < N; ++i) {
        if (count >= hi) break;
        cout << arr[i] << ' ';
        count++;
    }
    cout << "\n";
}
 
/********* DEBUG *********/

struct nd{
    int node;
    ld cst;
    int uses;
};

struct cmp {
    bool operator()(const nd &x, const nd &y){
        return x.uses == y.uses ? x.cst > y.cst : x.uses > y.uses;
    }
};

const ll inf = 1e18;
const int MOD = 1e9+7;
const int MOD2 = 998244353;
const int mxN = 200005;

double solve(int N, int M, int K, int H, vector<int> x, vector<int>y, vector<int> c, vector<int> power){
    K = min(K, 70);
    ld ans = 1e18;
    // cost, node, uses
    priority_queue<nd, vector<nd>, cmp> pq;
    pq.push({0,0,0});

    // cost, node
    vector<vector<pair<ld,int>>> adj(N);
    for (int i = 0; i < M; i++){
        adj[x[i]].pb({c[i], y[i]});
        adj[y[i]].pb({c[i], x[i]});
    }
    // find starts
    queue<int> q;
    vector<bool> visited(N, false);
    visited[0] = true;
    q.push(0);

    while (q.size()){
        int nd = q.front(); q.pop();

        if (power[nd] == 0){
            pq.push({nd,0,0});
        }

        for (auto &x : adj[nd]){
            if (x.second == H)
            continue;

            if (!visited[x.second]){
                visited[x.second] = true;
                q.push(x.second);
            }
        }
    }

    vector<vector<bool>> seen(N, vector<bool>(K+1, false));
    int cl = 0;
    while (pq.size()){
        auto x = pq.top(); pq.pop();
        ld cst = x.cst;
        int nd = x.node;
        int uses = x.uses;
        //cout << "nd, cst, use: " << nd << ' ' << cst << ' ' << uses << "\n";
        if (nd == H){
            ans = min(ans, cst);
            continue;
        }
        
        if (seen[nd][uses])
        continue;

        seen[nd][uses] = true;

        // cost, node
        for (auto &x : adj[nd]){
            ld Ncst = x.first;
            int Nnd = x.second;

            if (!seen[Nnd][uses]){
                pq.push({Nnd, cst+Ncst, uses});
            }

            if (power[Nnd] == 2 && uses < K && !seen[Nnd][uses+1]){
                pq.push({Nnd, (cst+Ncst)/2, uses+1});
            }
        }
    }

    return ans >= 1e18 ? -1 : (double)ans;
}

• 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