Submission #1155823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155823		ProtonDecay314	사이버랜드 (APIO23_cyberland)	C++20	97 / 100	3045 ms	14068 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pi> vpi;
typedef vector<vpi> vvpi;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back

typedef double ld;

typedef vector<double> vd;
typedef pair<double, int> pdi;

typedef vector<ld> vld;
typedef pair<ld, int> pldi;

const int max_K = 70;

template<typename T>
void print_vec(const vector<T>& v) {
    for(T vv : v) cerr << vv << " ";
    cerr << endl;
}

double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) {
    vvpi adj;
    
    K = min(K, max_K); // ! clamping K to a certain maximum

    for(int i = 0; i < N; i++) {
        vpi adjr;
        adj.pb(adjr);
    }

    for(int i = 0; i < M; i++) {
        adj[x[i]].pb({y[i], c[i]});
        adj[y[i]].pb({x[i], c[i]});
        
        // Divide by 2 ability
        // if(arr[x[i]] == 2) {
        //     adj[y[i]].pb({x[i], c[i]});
        // }
    }

    // Run BFS to see which are part of the same connected component
    vb visitable(N, false);
    queue<int> q;
    q.push(0);

    while(!q.empty()) {
        int i = q.front();
        q.pop();
        if(visitable[i]) continue;
        visitable[i] = true;
        if(i == H) continue;

        for(auto [j, _] : adj[i]) q.push(j);
    }

    if(!visitable[H]) return -1;
    
    // Find all superpower countries
    vi set_0;
    vi div_2;
    for(int i = 0; i < N; i++) {
        if(!visitable[i]) continue;
        if(arr[i] == 0) set_0.pb(i);
        if(arr[i] == 2) div_2.pb(i);
    }

    // Populate distance array
    ld ans = INF(ld);
    vld dist(N, INF(ld));
    typedef priority_queue<pldi, vector<pldi>, greater<pldi>> PQ; // ! greater is used for min priority queue
    PQ pq;
    
    for(int v : set_0) {
        pq.push({0.0L, v});
        dist[v] = 0.0L;
    }
    pq.push({0.0L, 0});
    dist[0] = 0.0L;

    for(int k_rep = 0; k_rep <= K; k_rep++) {
        // Run Dijkstra's on the new distances
        vb vis(N, false);

        while(!pq.empty()) {
            auto [cd, i] = pq.top();
            // cerr << cd << " " << i << endl;
            pq.pop();

            if(vis[i]) continue;
            vis[i] = true;
            dist[i] = cd;
            if(i == H) continue;

            for(auto [j, cost] : adj[i]) {
                pq.push({cd + (ld)(cost), j});
            }
        }

        // print_vec(dist);

        ans = min(ans, dist[H]);

        // Apply powerups
        vld newdist(N, INF(ld));

        for(int i : set_0) {
            newdist[i] = 0.0L;
            pq.push({0.0L, i});
        }

        for(int i : div_2) {
            ld min_dist = INF(ld);

            // if(dist[i] != INF(ld)) min_dist = dist[i] * 0.5L;

            for(auto [j, cost] : adj[i]) {
                /*
                For each neighbor of a divide-by-2 node,
                if it was reached, consider the cost
                */
                
                if(dist[j] != INF(ld) && j != H) {
                    min_dist = min(min_dist, (dist[j] + (ld)(cost)) * 0.5);
                }
            }

            // min_dist = min(min_dist, dist[i]);

            newdist[i] = min_dist;

            if(min_dist != INF(ld)) {
                pq.push({min_dist, i});
            }
        }

        // Consider the other nodes
        for(int i = 0; i < N; i++) {
            if(!visitable[i]) continue;

            pq.push({dist[i], i});
            newdist[i] = min(newdist[i], dist[i]);
        }

        dist = newdist;
    }
    
    return (ans == INF(double) ? -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: 0 / 3