Submission

Score: 100

User: tull

Problemset: รัฐบาล

Language: cpp

Time: 0.004 second

Submitted On: 2026-06-01 00:29:21

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long
const long long INF = 4e18;

struct DSU {
    vector<int> par, sz;

    DSU(int n) : par(n + 1), sz(n + 1, 1) {
        iota(par.begin(), par.end(), 0);
    }

    int Find(int a) {
        if (par[a] == a) return a;
        return par[a] = Find(par[a]);
    }

    bool Same(int a, int b) {
        return Find(a) == Find(b);
    }

    void Union(int a, int b) {
        a = Find(a);
        b = Find(b);

        if (a == b) return;

        if (sz[b] > sz[a]) swap(a, b);

        par[b] = a;
        sz[a] += sz[b];
    }
};

struct Edge {
    int w, u, v, id;
};

pair<int, vector<int>> MST(vector<Edge>& edges, int n, int banId, bool record) {
    DSU dsu(n);

    int sum = 0;
    int cnt = 0;
    vector<int> usedEdges;

    for (auto& e : edges) {
        if (e.id == banId) continue;

        if (!dsu.Same(e.u, e.v)) {
            dsu.Union(e.u, e.v);
            sum += e.w;
            cnt++;

            if (record) {
                usedEdges.push_back(e.id);
            }
        }
    }

    if (cnt != n - 1) {
        return {INF, {}};
    }

    return {sum, usedEdges};
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<Edge> edges(m);

    for (int i = 0; i < m; i++) {
        int l, r, x;
        cin >> l >> r >> x;

        if (l > r) swap(l, r);

        edges[i] = {x, l, r, i};
    }

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        if (a.w != b.w) return a.w < b.w;
        return a.id < b.id;
    });

    auto [mstWeight, mstEdges] = MST(edges, n, -1, true);

    cout << mstWeight << ' ';

    int secondMST = INF;

    for (int id : mstEdges) {
        auto [weight, unused] = MST(edges, n, id, false);
        secondMST = min(secondMST, weight);
    }

    if (secondMST == INF) {
        cout << -1;
    } else {
        cout << secondMST;
    }
}