Submission #976687

#	Time	Username	Problem	Language	Result	Execution time	Memory
976687		Mr_Husanboy	Cyberland (APIO23_cyberland)	C++17	0 / 100	25 ms	7252 KiB

cyberland

#include "cyberland.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define all(a) (a).begin(), (a).end()
#ifdef LOCAL
#include "debugger.cpp"
#else
#define debug(...)
#endif

const ll infl = 1e18;

struct DSU{
    vector<int> par, sz; int n;
    DSU (int _n){
        n = _n;
        par.resize(n);
        iota(all(par), 0);
        sz.assign(n, 1);
    }
    DSU (){}
    int get(int a){
        return (par[a] == a ? a : par[a] = get(par[a]));
    }

    void init(int _n){
        n = _n;
        par.resize(n);
        iota(all(par), 0);
        sz.assign(n, 1);
    }

    void unite(int a, int b){
        a = get(a);
        b = get(b);
        if(a == b) return;
        if(sz[a] < sz[b]) swap(a,b);
        sz[a] += sz[b];
        par[b] = a;
    }

    void link(int a, int b){
        a = get(a); b = get(b);
        if(a == b) return;
        sz[b] += sz[a];
        par[a] = b;
    }
};


double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    vector<vector<pair<int,double>>> g(n);
    DSU ds(n);
    for(int i = 0; i < m; i ++){
        g[x[i]].push_back({y[i], c[i]});
        g[y[i]].push_back({x[i], c[i]});
        ds.unite(x[i], y[i]);
    }
    if(ds.get(0) != ds.get(n - 1)){
        return -1;
    }

    priority_queue<pair<double, int>> q;
    vector<bool> vis(n);
    vector<double> dis(n, infl);
    dis[n - 1] = 0;
    q.push({0, n - 1});
    double mn = infl;

    while(!q.empty()){
        int t = q.top().second; q.pop();
        if(vis[t]) continue;
        vis[t] = 1;

        for(auto [u, w] : g[t]){
            if(arr[u] == 0) mn = min(mn, dis[t] + w);
            if(dis[u] > dis[t] + w){
                dis[u] = dis[t] + w;
                q.push({-dis[u], u});
            }
        }
    }
    debug(dis);
    return min(mn, dis[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