Submission #993258


Source Code Expand

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(int x) { return 31 - __builtin_clz(x); }

struct UnionFind {
    vector<int> ig;
    vector<vector<int>> gi;
    int gn;
    UnionFind(int N) {
        ig.resize(N); gi.resize(N);
        for (int i = 0; i < N; i++) {
            ig[i] = i; gi[i] = {i};
        }
        gn = N;
    }
    void merge(int a, int b) {
        if (same(a, b)) return;
        gn--;
        int x = ig[a], y = ig[b];
        if (gi[x].size() < gi[y].size()) swap(x, y);
        for (int j: gi[y]) {
            ig[j] = x;
        }
        gi[x].insert(gi[x].end(), gi[y].begin(), gi[y].end());
        gi[y].clear();
    }
    bool same(int a, int b) {
        return ig[a] == ig[b];
    }
};

int main() {
    ios::sync_with_stdio(0);
    cout << setprecision(20);
    int n, q;
    cin >> n >> q;
    using T = tuple<ll, int, int, bool>;
    priority_queue<T, vector<T>, greater<T>> que;
    for (int i = 0; i < q; i++) {
        int a, b; ll c;
        cin >> a >> b >> c;
        que.push(T(c, a, b, false));
    }

    UnionFind uf(n);
    ll ans = 0;
    while (uf.gn > 1) {
        if (que.size() == 0) break;
        int a, b; ll c; bool f;
        tie(c, a, b, f) = que.top(); que.pop();
//        cout << a << " " << b << " " << c << endl;
        if (!uf.same(a, b)) {
            uf.merge(a, b);
            ans += c;
            que.push(T(c+1, b, (a+1)%n, false));
        } else {
            if (!f) {
                que.push(T(c+1, b, (a+1)%n, true));
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User yosupo
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 2013 Byte
Status AC
Exec Time 247 ms
Memory 19436 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 33
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
all sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt
Case Name Status Exec Time Memory
01-01.txt AC 2 ms 256 KB
01-02.txt AC 67 ms 6512 KB
01-03.txt AC 131 ms 18668 KB
01-04.txt AC 30 ms 13180 KB
01-05.txt AC 34 ms 13180 KB
01-06.txt AC 38 ms 13180 KB
01-07.txt AC 42 ms 14012 KB
01-08.txt AC 48 ms 13860 KB
01-09.txt AC 70 ms 14232 KB
01-10.txt AC 115 ms 16496 KB
01-11.txt AC 116 ms 12140 KB
01-12.txt AC 161 ms 19180 KB
01-13.txt AC 160 ms 18668 KB
01-14.txt AC 161 ms 19436 KB
01-15.txt AC 161 ms 18924 KB
01-16.txt AC 162 ms 18924 KB
01-17.txt AC 162 ms 19308 KB
01-18.txt AC 136 ms 18412 KB
01-19.txt AC 38 ms 14096 KB
01-20.txt AC 76 ms 14096 KB
01-21.txt AC 128 ms 16116 KB
01-22.txt AC 243 ms 19180 KB
01-23.txt AC 247 ms 18668 KB
01-24.txt AC 41 ms 13560 KB
01-25.txt AC 187 ms 18540 KB
01-26.txt AC 36 ms 13180 KB
01-27.txt AC 64 ms 14348 KB
01-28.txt AC 157 ms 17136 KB
01-29.txt AC 190 ms 12780 KB
01-30.txt AC 221 ms 18796 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 3 ms 256 KB
sample-03.txt AC 2 ms 256 KB