Submission #995321

---

Source Code Expand

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <set>
using namespace std;

typedef long long llong;

const int N = 1000500;

int n;

struct chain {
    int a, b, c;
    void promote() {
        if ((++a) >= n)
            a = 0;
        if ((++b) >= n)
            b = 0;
        c += 2;
    }
};

int par[N], rnk[N];

int get(int x) {
    return (x == par[x]) ? x : (par[x] = get(par[x]));
}

bool merge(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b)
        return false;
    if (rnk[a] > rnk[b]) {
        swap(a, b);
    }
    if (rnk[a] == rnk[b])
        rnk[b]++;
    par[a] = b;
    return true;
}

int cpt = 0;
chain C[N];

struct evt {
    int t;
    int i;
};

int ept = 0;
evt E[N];

void add_chain(int a, int b, int c) {
    E[ept++] = {c, cpt};
    C[cpt++] = {a, b, c};
}

set<int> ids[2];

int main() {
    int q;
    int mn = 1e9 + 42;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < q; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        mn = min(mn, c);
        add_chain(a, b, c);
        add_chain((a + 1) % n, b, c + 1);
    }
    sort(E, E + ept, [] (evt a, evt b) { return a.t < b.t; } );
    int pt = 0;
    llong ans = 0;

    for (int i = 0; i < n; i++)
        par[i] = i;

    int cnt = 0;
    for (int t = mn; cnt < n - 1; t++) {
        while (pt != ept && E[pt].t <= t) {
            ids[t % 2].insert(E[pt].i);
            pt++;
        }
        auto& cur = ids[t % 2];
        vector<int> todel;
        for (int i : cur) {
            if (!merge(C[i].a, C[i].b)) {
                todel.push_back(i);
            } else {
                ans += C[i].c;
                assert(C[i].c == t);
                C[i].promote();
                cnt++;
            }
        }
        for (int i : todel)
            cur.erase(i);
    }
    printf("%lld\n", ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:65:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
                           ^
./Main.cpp:68:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
                                      ^

Judge Result