Submission #1153400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153400		tapilyoca	Cyberland (APIO23_cyberland)	C++20	21 / 100	90 ms	7496 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using ld = long double;


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<vector<pair<ll,ll>>> adj(N+1);
    for(int i = 0; i < M; i++){
        ll a = x[i];
        ll b = y[i];
        ll w = c[i];
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }


    // first BFS: check which 0s we can actually reach
    vector<bool> vis(N+1,0);

    vis[0] = 1;
    queue<ll> q;
    q.push(0);
    while(!q.empty()){
        ll at = q.front();
        q.pop();
        for(pair<ll,ll> p : adj[at]){
            ll node = p.first;
            if(vis[node]) continue;
            if(node == H) continue;

            vis[node] = 1;
            q.push(node);
        }
    }
    assert(!vis[H]);

    // now djk from A
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    vector<ll> dist(N+1, 1e18);
    pq.push({H,0});
    dist[H] = 0;

    while(!pq.empty()){
        ll node = pq.top().first;
        pq.pop();
        for(pair<ll,ll> Z : adj[node]){
            ll weight = Z.second;
            ll place = Z.first;
            if(weight+dist[node] < dist[place]){
                dist[place] = weight+dist[node];
                pq.push({place,dist[place]});
            }
        }
    }

    ll mn = 0;

    for(int i = 0;i < N; i++){
        cerr << dist[i] << " ";
    } cerr << endl;

    for(int i = 0; i < N; i++){
        if(i == H) continue; //cyberland itself
        if(!vis[i]) continue; // not visited
        if(arr[i] != 0 and i != 0) continue; // not a start point

        if(!mn) mn = dist[i];
        else mn = min(mn, dist[i]);
    }
    return mn;
    
    // return -1;
}

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