Submission #1160744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160744		LolkasMeep	Cyberland (APIO23_cyberland)	C++20	0 / 100	26 ms	15944 KiB

cyberland

#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int>
    y, std::vector<int> c, std::vector<int> arr){
    vector<unordered_map<int, double>> adjList(N);
    
    for(int i = 0; i < M; i++){
        adjList[x[i]][y[i]] = c[i];
        adjList[y[i]][x[i]] = c[i];
    }

    vector<bool> connected(N);
    deque<int> dq;
    dq.push_back(0);
    connected[0] = true;

    while(!dq.empty()){
        int node = dq.front();
        dq.pop_front();
        for(const pair<int, double> &nxtPr : adjList[node]){
            int nxtNode = nxtPr.first;
            if(connected[nxtNode]) continue;
            if(nxtNode == H) continue;
            connected[nxtNode] = true;
            dq.push_back(nxtNode);
        }
    }


    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<double> dist(N, DBL_MAX);
    pq.push(make_pair(H, 0));
    dist[H] = 0;

    while(!pq.empty()){
        pair<int, int> pr = pq.top();
        pq.pop();
        // cout << pr.first << ' ' << pr.second << '\n';
        
        for(const pair<int, double> &nxtPr : adjList[pr.first]){
            
            int nxtNode = nxtPr.first;
            double newDist = nxtPr.second;
            // cout << nxtPr.first << ' ' << dist[nxtNode] << ' ' << connected[nxtNode] << '\n';
            if(newDist >= dist[nxtNode]) continue;
            if(!connected[nxtNode]) continue;

            dist[nxtNode] = newDist;
            pq.push(make_pair(nxtNode, newDist));
            
        }
    }

    double mnDist = DBL_MAX;

    for(int i = 0; i < N; i++){
        if((arr[i] == 0 && connected[i]) || i == 0)
            mnDist = min(mnDist, dist[i]);
    }

    if(mnDist == DBL_MAX) mnDist = -1;

    return mnDist;
}

// int main(){
//     cout << solve(3, 1, 30, 2, {1}, {2}, {12}, {1, 2, 1});
//     return 0;
// }

• 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