Submission #1156074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156074		lrnnz	Cyberland (APIO23_cyberland)	C++20	0 / 100	20 ms	6212 KiB

cyberland

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back
#define ll long long
#define ui uint64_t
#define ar array
#define us unordered_set
#define cont(set, element) ((set).find(element) != (set).end())
 
/********* DEBUG *********/
template <typename T>
void outvec(const vector<T>& Z, int hi = INT_MAX) {
    int count = 0;
    for (const T& x : Z) {
        if (count >= hi) break;
        cout << x << ' ';
        count++;
    }
    cout << "\n";
}

// overloaded function for raw arrays
template <typename T, size_t N>
void outvec(const T (&arr)[N], int hi = INT_MAX) {
    int count = 0;
    for (size_t i = 0; i < N; ++i) {
        if (count >= hi) break;
        cout << arr[i] << ' ';
        count++;
    }
    cout << "\n";
}
 
/********* DEBUG *********/

const ll inf = 1e18;
const int MOD = 1e9+7;
const int MOD2 = 998244353;
const int mxN = 200005;


// Subtask arr ∈ {0,1}
// DSU, find all possible starting places
// Push all starting nodes to Djikstra


int parent[100005];

int _find(int x){
    if (parent[x] != x)
    parent[x] = _find(parent[x]);

    return parent[x];
}

void _uni(int x, int y){
    x = _find(x);
    y = _find(y);

    parent[x] = y;
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    for (int i = 0; i < N; i++){
        parent[i] = i;
    }
    // node, cost
    vector<vector<pair<int,int>>> adj(N);
    unordered_set<int> starts = {0};

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

        if (x[i] != H && y[i] != H){
            _uni(x[i], y[i]);
        }

        if (arr[x[i]] == 0 && _find(x[i]) == _find(0))
        starts.insert(x[i]);

        if (arr[y[i]] == 0 && _find(y[i]) == _find(0))
        starts.insert(y[i]);
    }

    // cost, node
    bool visited[N];
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> minheap;
    for (auto &x : starts){
        minheap.push({0, x});
        visited[x] = true;
    }
    
    
    while (minheap.size()){
        vector<int> x = minheap.top(); minheap.pop();
        int cst = x[0];
        int nd = x[1];

        if (nd == H)
        return cst;

        for (auto &x : adj[nd]){
            if (visited[x.first])
            continue;

            visited[x.first] = true;
            vector<int> y(2);
            y[0] = cst+x.second;
            y[1] = x.first;
            minheap.push(y);
        }
    }

    return -1;
}

• 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