Submission #1152825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152825		elipsen	Cyberland (APIO23_cyberland)	C++20	49 / 100	113 ms	11092 KiB

cyberland

#include "cyberland.h"

#include <vector>
#include <unordered_map>
#include <queue>
#include <utility>
#define v vector
#define u_m unordered_map
#define q queue
#define p_q priority_queue
#define p pair
#define ll long long
using namespace std;

class WorldMap {
    const ll tempInf = 1000000000000000;
    int countryCount; int cyberland;
    u_m<int, v<p<int, int>>> friends;
    v<ll> dspaSourceResult;
    u_m<int, ll> halvers; u_m<int, ll> customHalvers;
    v<int> powers;
    
    
    public:
    // Initialize the world map
    WorldMap(int countries, int destinationIndex) {
        countryCount = countries;
        cyberland = destinationIndex;
        friends.clear(); dspaSourceResult.clear(); halvers.clear(); customHalvers.clear(); powers.clear();
    }

    void connect(int friend1, int friend2, int distance) {
        friends[friend1].push_back(make_pair(friend2, distance));
        friends[friend2].push_back(make_pair(friend1, distance));
    }

    void notePowers(v<int> arr) {
        powers = arr;
    }

    void dspaSource() {
        // Initialize stuff
        dspaSourceResult.clear(); dspaSourceResult.resize(countryCount, tempInf);
        p_q<p<ll, int>, v<p<ll, int>>, greater<p<ll, int>>> dspaQueue;
        dspaQueue.push(make_pair(0, 0));
        dspaSourceResult[0] = 0;

        int selected; int friendID; int friendDist;
        // Go through the queue 
        while (!(dspaQueue.empty())) {
            selected = dspaQueue.top().second; dspaQueue.pop();
            // Go through the first-in-line's friends
            for (p<int, int> fren : friends[selected]) {
                friendID = fren.first; friendDist = fren.second;
                // If the friend has 0-powers
                if (powers[friendID] == 0) {
                    // Propagate only if it hasn't been hit before
                    if (dspaSourceResult[friendID] > 0) {
                        dspaSourceResult[friendID] = 0;
                        // Note that we cannot leave Cyberland
                        if (friendID != cyberland) dspaQueue.push(make_pair(0, friendID));
                    }
                } else {
                    // Propagate only if the value changes
                    if (dspaSourceResult[selected] + friendDist < dspaSourceResult[friendID]) {
                        dspaSourceResult[friendID] = dspaSourceResult[selected] + friendDist;
                        // Note that we cannot leave Cyberland
                        if (friendID != cyberland) dspaQueue.push(make_pair(dspaSourceResult[friendID], friendID));
                    }
                }
            }
        }
    }

    void dspaCustom(int halverInd) {
        // Initialize stuff
        v<ll> dspaCustomResult(countryCount, tempInf);
        p_q<p<ll, int>, v<p<ll, int>>, greater<p<ll, int>>> dspaQueue;
        customHalvers.clear();
        dspaQueue.push(make_pair(0, halverInd));
        dspaCustomResult[halverInd] = 0;

        int selected; int friendID; int friendDist;
        // Go through the queue
        while (!(dspaQueue.empty())) {
            selected = dspaQueue.top().second; dspaQueue.pop();
            // Go through the first-in-line's friends
            for (p<int, int> fren : friends[selected]) {
                friendID = fren.first; friendDist = fren.second;
                // Propagate only if the value changes
                if (dspaCustomResult[selected] + friendDist < dspaCustomResult[friendID]) {
                    dspaCustomResult[friendID] = dspaCustomResult[selected] + friendDist;
                    // Note that we cannot leave Cyberland, & it's sub-optimal to pass by a 2-power for the path
                    if ((friendID != cyberland) && (powers[friendID] == 2)) dspaQueue.push(make_pair(dspaCustomResult[friendID], friendID));
                    // return if friend's power is 2 - this shall be the closest friend
                    if (powers[friendID] == 2) customHalvers[friendID] = dspaCustomResult[friendID];
                }
            }
        }
    }

    void dspaDestination() {
        // Initialize stuff
        v<ll> dspaDestinationResult(countryCount, tempInf);
        p_q<p<ll, int>, v<p<ll, int>>, greater<p<ll, int>>> dspaQueue;
        q<int> halverQueue;
        dspaQueue.push(make_pair(0, cyberland));
        dspaDestinationResult[cyberland] = 0;

        int selected; int friendID; int friendDist;
        // Go through the queue
        while (!(dspaQueue.empty())) {
            selected = dspaQueue.top().second; dspaQueue.pop();
            // Go through the first-in-line's friends
            for (p<int, int> fren : friends[selected]) {
                friendID = fren.first; friendDist = fren.second;
                // Propagate only if the value changes
                if (dspaDestinationResult[selected] + friendDist < dspaDestinationResult[friendID]) {
                    dspaDestinationResult[friendID] = dspaDestinationResult[selected] + friendDist;
                    // Log if friend's power is 2
                    dspaQueue.push(make_pair(dspaDestinationResult[friendID], friendID));
                    if (powers[friendID] == 2) halverQueue.push(friendID);
                }
            }
        }

        // Deal with the queue for 2-powers
        while (!(halverQueue.empty())) {
            selected = halverQueue.front(); halverQueue.pop();
            halvers[selected] = dspaDestinationResult[selected];
        }
    }

    double minimize(int selected, int twoPower, int distLeft) {
        if (twoPower == 0) return selected;
        int friendID; ll friendDist; double base = dspaSourceResult[selected]; ll minDist = tempInf;
        base = base / 2; twoPower--;
         double minReturn = base + distLeft;
        for(p<int, int> fren : friends[selected]) {
            friendID = fren.first; friendDist = fren.second;
            if (friendID != cyberland) minDist = min(minDist, friendDist);
        }
        if (minDist != tempInf) minReturn = min(minReturn, distLeft + minDist * 2 + div2(base - minDist * 2, twoPower));
        dspaCustom(selected);
        for (pair<int, ll> halver : customHalvers) {
            minDist = halver.second; ll distLeft2 = halvers[halver.first];
            if (minDist != tempInf) minReturn = min(minReturn, distLeft2 + minDist + div2(base - minDist, twoPower));
        }
        return minReturn;
    }

    double div2(double ans, int expo) {
        double k = 2;
        while (expo != 0) {
            if (expo & 1) ans = ans / k;
            expo = expo >> 1; k = k * k;
        }
        return ans;
    }

    double determinePath(int twoPower) {
        // Perform DijkstraSPA once from source, apply 0 and 1 rules
        dspaSource();
        // Perform DijkstraSPA once again, stop at 0s and 2s, record 2s
        dspaDestination();
        // Then consolidate hereon
        if (dspaSourceResult[cyberland] == tempInf) return -1;
        
        double minimum = dspaSourceResult[cyberland];
        for (auto info : halvers) {
            int halver = info.first; ll distLeft = info.second;
            if (dspaSourceResult[halver] == tempInf) continue;
            double contender = minimize(halver, twoPower, distLeft);
            minimum = min(minimum, contender);
        }

        return minimum;
    }

};

double solve(int N, int M, int K, int H, v<int> x, v<int> y, v<int> c, v<int> arr) {
    // Rename every int to something more descriptive
    int countryCount = N; int roadCount = M; int bitShifter = K; int cyberLocation = H;
    WorldMap theRoadToCyberland(countryCount, cyberLocation);
    for (int road = 0; road < roadCount; road++)
        theRoadToCyberland.connect(x[road], y[road], c[road]);
    theRoadToCyberland.notePowers(arr);
    return theRoadToCyberland.determinePath(bitShifter);
}

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