Submission #1155679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155679		ProtonDecay314	Cyberland (APIO23_cyberland)	C++20	0 / 100	3092 ms	9140 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 vector<double> vd;
typedef pair<double, int> pdi;

vvpi adj;

const int max_K = 70;

double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) {
    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;

        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
    double ans = INF(double);
    vd dist(N, INF(double));
    typedef priority_queue<pdi, vector<pdi>, greater<pdi>> PQ; // ! greater is used for min priority queue
    PQ pq;
    
    for(int v : set_0) {
        pq.push({0.0, v});
        dist[v] = 0.0;
    }
    pq.push({0.0, 0});
    dist[0] = 0.0;

    for(int k_rep = 0; k_rep <= K; k_rep++) {
        // Reset distance function
        if(k_rep > 0) {
            vd newdist(N, INF(double));

            newdist[0] = 0.0;
            pq.push({0.0, 0});

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

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

                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(double)) {
                        min_dist = min(min_dist, (dist[j] + (double)(cost)) * 0.5);
                    }
                }

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

                newdist[i] = min_dist;

                if(min_dist != INF(double)) {
                    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;
        }
        
        // 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;

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

        ans = min(ans, dist[H]);
    }
    
    return (ans == INF(double) ? -1 : ans);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 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