Submission #1150624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150624		QuantumK9	Cyberland (APIO23_cyberland)	C++20	44 / 100	27 ms	8516 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

const ll MAX = 1e15;

int _H;
vector<int> zeroes;
vector<vector<pair<int, ll> > > connect;
vector<bool> explored;

void explore(int i, vector<int> &a) {
    explored[i] = true;

    if (a[i] == 0) { zeroes.pb(i); }

    if (i == _H) { return; }

    for (pair<int, ll> jp : connect[i]) { 
        int j = jp.f;
        if (!explored[j]) { explore(j, a); }
    }
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {

    zeroes.clear();
    connect.clear();
    explored.clear();

    // set-up
    _H = H;
    connect.resize(N);
    explored.resize(N, false);

    for (int i = 0; i < M; i++) {
        connect[x[i]].pb(mp(y[i], c[i]));
        connect[y[i]].pb(mp(x[i], c[i]));
    }

    // find the cities that are connected (and in-play)
    explore(0, arr);

    if (!explored[H]) { return -1; }

    // run djikstra's from H as the source
    // the answer is the minimum among all the 'zeroes'
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    vector<ll> dists(N, MAX); // distance of a city to H

    dists[H] = 0;
    pq.push(mp(0, H));

    while(!pq.empty()) {
        pair<ll, int> p = pq.top(); pq.pop();
        ll d = p.f; int i = p.s;

        if (dists[i] < d) { continue; }

        for (pair<int, ll> jp : connect[i]) {
            if (dists[jp.f] > d + jp.s) {
                dists[jp.f] = d + jp.s;
                pq.push(mp(d + jp.s, jp.f));
            }
        }
    }

    ll ans = dists[0];
    for (int i : zeroes) { ans = min(ans, dists[i]); }

    return ans;
}

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