Submission #1153670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153670		elipsen	Cyberland (APIO23_cyberland)	C++20	0 / 100	3109 ms	1051960 KiB

cyberland

#include "cyberland.h"

#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <utility>
#define v vector
#define s set
#define u_s unordered_set
#define m map
#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 int maxShift = 100000;
    const ll tempInf = 1000000000000000;
    int countryCount; int cyberland; double minimum;
    v<m<int, ll>> friends;
    v<ll> dspaSourceResult;
    u_m<int, ll> halvers;
    v<int> powers;
    
    
    public:
    // Initialize the world map
    WorldMap(int countries, int destinationIndex) {
        countryCount = countries;
        cyberland = destinationIndex;
        minimum = tempInf;
        friends.clear(); friends.resize(countryCount);
        dspaSourceResult.clear(); halvers.clear(); powers.clear();
    }

    void connect(int friend1, int friend2, int distance) {
        friends[friend1][friend2] = distance;
        friends[friend2][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, ll> 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 condense() {
        // For each node, if its power is not 2 or if it's not cyberland, remove and reconnect
        // For each node left, remove all its connections to removed nodes
        for (int i = 0; i < countryCount; i++) {
            if ((i == cyberland) || (powers[i] == 2)) continue;
            for (p<int, ll> fren1 : friends[i]) {
                int f1ID = fren1.first; ll f1d = fren1.second;
                for (p<int, ll> fren2 : friends[i]) {
                    int f2ID = fren2.first; ll f2d = fren2.second;
                    if (f1ID != f2ID) {
                        ll total = f1d + f2d;
                        friends[f1ID][f2ID] = (friends[f1ID][f2ID] == 0) ? total : min(friends[f1ID][f2ID], total);
                    }
                    if (f1ID != cyberland) friends[f1ID][f1ID] = (friends[f1ID][f1ID] == 0) ? f1d * 2 : min(friends[f1ID][f1ID], f1d * 2);
                    if (f2ID != cyberland) friends[f2ID][f2ID] = (friends[f2ID][f2ID] == 0) ? f2d * 2 : min(friends[f2ID][f2ID], f2d * 2);
                }
            }
        }

        for (int i = 0; i < countryCount; i++) {
            if ((i == cyberland) || (powers[i] == 2)) continue;
            friends[i] = {};
        }

        for (int i = 0; i < countryCount; i++) {
            for (p<int, ll> fren : friends[i]) {
                int friendID = fren.first;
                if ((friendID == cyberland) || (powers[friendID] == 2)) continue;
                friends[i].erase(friendID);
            }
        }
    }

    void dspaDestination() {
        // Initialize stuff
        v<ll> dspaDestinationResult(countryCount, tempInf);
        p_q<p<ll, int>, v<p<ll, int>>, greater<p<ll, int>>> dspaQueue;
        u_s<int> halverSet;
        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, ll> 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) halverSet.insert(friendID);
                }
            }
        }

        // Deal with the queue for 2-powers
        for (auto selected: halverSet) halvers[selected] = dspaDestinationResult[selected];
    }

    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;
    }

    bool navigate(int halverInd, double currDistance, double lastDistance, int halvesUsed, int maxHalves) {
        // Navigating from Cyberland back to home; first update
        double newDist = currDistance + lastDistance;
        minimum = min(minimum, newDist + div2(dspaSourceResult[halverInd], halvesUsed));

        // Then try to minimize saved path length
        if ((halvesUsed < maxHalves) && (newDist < minimum - max(minimum * 1.0E-6, 1.0E-6))) {
            minimum = min(minimum, newDist + div2(dspaSourceResult[halverInd], halvesUsed + 1));

            // If maxHalves has not been reached, go through each friend
            // Initialize stuff
            v<double> dspaCustomResult(countryCount, tempInf);
            p_q<p<double, int>, v<p<double, int>>, greater<p<double, int>>> dspaQueue;
            dspaQueue.push(make_pair(0, halverInd));
            dspaCustomResult[halverInd] = 0;

            int selected; double selectedDist; int friendID; double friendDist; bool selfSatisfaction = false;
            // Go through the queue
            while (!(dspaQueue.empty())) {
                selected = dspaQueue.top().second; selectedDist = dspaQueue.top().first; dspaQueue.pop();

                // Iterate to next loop
                if (powers[selected] == 2) {
                    if (dspaSourceResult[selected] != tempInf) {
                        if ((selectedDist != 0) && (selectedDist != tempInf)) {
                            bool get = navigate(selected, newDist, selectedDist, halvesUsed + 1, maxHalves);
                            if (get) break;
                        }
                    }
                    if ((selected == halverInd) && (selectedDist != 0)) continue;
                }

                // Go through the first-in-line's friends
                for (p<int, ll> fren : friends[selected]) {
                    friendID = fren.first; friendDist = div2(fren.second, halvesUsed + 1);
                    // Propagate only if the value changes
                    if (dspaCustomResult[selected] + friendDist < dspaCustomResult[friendID]) {
                        dspaCustomResult[friendID] = dspaCustomResult[selected] + friendDist;
                        // Note that we cannot leave Cyberland
                        if (friendID != cyberland) dspaQueue.push(make_pair(dspaCustomResult[friendID], friendID));
                    } else if ((!(selfSatisfaction)) && (friendID == halverInd)) {
                        // If it loops to itself, return that as well
                        dspaQueue.push(make_pair(dspaCustomResult[selected] + friendDist, halverInd));
                        selfSatisfaction = true;
                    }
                }
            }
            
            return false;
        } else return true;
    }

    double determinePath(int twoPower) {
        // Perform DijkstraSPA once from source, apply 0 and 1 rules
        dspaSource();
        // Condense the map...?
        condense();
        // Perform DijkstraSPA once from destination, record 2s
        dspaDestination();
        
        // Then consolidate hereon
        if (dspaSourceResult[cyberland] == tempInf) return -1;
        // If Cyberland is reachable
        p_q<p<ll, int>, v<p<ll, int>>, greater<p<ll, int>>> dfsFromDestinationQueue;
        minimum = dspaSourceResult[cyberland];
        for (auto info : halvers) dfsFromDestinationQueue.push(make_pair(info.second, info.first));
        twoPower = min(twoPower, maxShift);
        // Go through each 2-power starting from destination, dfs-style
        p<ll, int> currentHalver;
        while (!(dfsFromDestinationQueue.empty())) {
            currentHalver = dfsFromDestinationQueue.top(); dfsFromDestinationQueue.pop();
            if ((currentHalver.first != tempInf) && (dspaSourceResult[currentHalver.second] != tempInf)) {
                bool get = navigate(currentHalver.second, 0, currentHalver.first, 0, twoPower);
                if (get) break;
            }
        }

        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: 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