Submission #5018658

---

Source Code Expand

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using std::cin;
using std::cout;
using LL = long long;
using pii = std::pair<int, int>;
using pip = std::pair<int, pii>;
const int MAXN = 2e5 + 10;

int f[MAXN];
std::vector<pii> G[MAXN];


int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

bool unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy)return false;
    f[fx] = fy;
    return true;
}

struct hh {
    size_t operator()(const pii &s) const {
        size_t out = 14695981039346656037ULL;
        static constexpr size_t mul = 1099511628211ULL;
        out = (out ^ s.first) * mul;
        out = (out ^ s.second) * mul;
        return out;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    std::priority_queue<pip, std::vector<pip>, std::greater<>> q;
    for (int i = 1; i <= n; ++i) f[i] = i;
    std::vector<pip> V(m);
    for (int i = 0, A, B, C; i < m; ++i) {
        cin >> A >> B >> C;
        V[i] = {C, {A, B}};
    }

    std::unordered_set<pii, hh> S;
    std::sort(begin(V), end(V));
    int C = V[0].fi;
    for (auto & i : V) {
        if (i.fi - C > n + n) break;
        G[i.fi - C].pb(i.se);
        S.insert(i.se);
    }

    int cnt = 0;
    LL ans = 0;
    for (int i = 0; cnt != n - 1; ++i) {
        pii p;
        for (auto it : G[i]) {
            if (unite(it.fi, it.se)) ans += i + C, cnt++;
            // cout << it.fi << it.se << std::endl;
            p = {it.se, (it.fi + 1) % n};
            if (S.find(p) != end(S)) continue;
            G[i + 1].pb(p);
            S.insert(p);
        }
    }
    cout << ans << "\n";
//    while (cnt != n - 1) {
//        pip p = q.top();
//        q.pop();
//        int c = p.fi, a = p.se.fi, b = p.se.se;
//        // cout << a << " " << b <<"\n";
//        if (S.find({a, b}) != end(S)) continue;
//        S.insert({a, b});
//        if (unite(a, b)) ans += c, cnt++;
//        q.push({c + 1, {b, (a + 1) % n}});
//    }
//    cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef trote
    freopen("../1.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

Submission Info

Judge Result