提出 #53123170

---

ソースコード 拡げる

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bitset>
#include <sstream>

using namespace std;
using namespace __gnu_pbds;

/* clang-format off */

/* TYPES  */
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define mii map<int, int>
#define si set<int>
#define sc set<char>

#define sz(x) (x).size()

/* FUNCTIONS */
#define feach(el, v) for(auto &el: v)
#define rep(i, n) for(int i=0;i<n;i++)
#define reprv(i, n) for(int i=n-1;i>=0;i--)
#define reps(i, s, e) for(int i=s;i<e;i++)
#define reprve(i, e, s) for(int i=e;i>=s;i--)

#define pb push_back
#define eb emplace_back

#define dec(zz) int (zz); cin >> zz;
#define decv(zz, n) vector<int> zz(n); for(int i=0;i<n;++i) cin >> zz[i];
#define decvn(zz, n) int n; cin >> n; vector<int> zz(n); for(int i=0;i<n;++i) cin >> zz[i];

typedef tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> oSet;

const int MAXN = 200020;
vector<int> parent(MAXN), rnk(MAXN);

void makeSets(int n) {
    rep(i, n) {
        parent[i] = i;
        rnk[i] = 0;
    }
}

int findSet(int v) {
    if (v == parent[v]) return v;
    return parent[v] = findSet(parent[v]);
}

void unionSets(int a, int b) {
    a = findSet(a), b = findSet(b);
    if (a != b) {
        if (rnk[a] < rnk[b]) swap(a, b);
        parent[b] = a;
        if (rnk[a] == rnk[b]) ++rnk[a];
    }
}

int main() {
    int n, q; cin >> n >> q;

    makeSets(n);

    map<ll, vector<int>> edges;
    rep(i, q) {
        ll compSz, cost; cin >> compSz >> cost;

        int vrt;
        rep(j, compSz) {
            cin >> vrt;
            edges[cost].push_back(vrt - 1);
        }
    }

    ll totalCost = 0;
    for (auto &[compCost, conComp]: edges) {
        int first = conComp[0];
        for (auto &vComp: conComp) {
            if (findSet(first) != findSet(vComp)) {
                totalCost += compCost;
                unionSets(first, vComp);
            }
        }
    }

    rep(i, n) {
        if (findSet(i) != findSet(0)) {
            cout << "-1";
            return 0;
        }
    }
    cout << totalCost;
    return 0;
}

提出情報

ジャッジ結果