Submission #5377235

---

Source Code Expand

#include<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}
struct UnionFind {
    int n, cc, *u;
    UnionFind() : n(0), cc(0), u(NULL) {}
    UnionFind(int n_) : n(n_), cc(n_) {
	u = new int[n_];
	memset(u, -1, sizeof (int) * n);
    }
    UnionFind(const UnionFind &y) : n(y.n), cc(y.cc) {
	u = new int[y.n];
	memcpy(u, y.u, sizeof (int) * n);
    }
    ~UnionFind() {
	delete[] u; u = NULL;
	n = cc = 0;
    }
    friend void swap(UnionFind &x, UnionFind &y) {
	swap(x.n, y.n); swap(x.cc, y.cc); swap(x.u, y.u);
    }
    UnionFind& operator=(UnionFind y) { 
	swap(*this, y);
	return *this;
    }
    int root(int x) {
	int y = x, t;
	while (u[y] >= 0) y = u[y];
	while (x != y) { t = u[x]; u[x] = y; x = t; }
	return y;
    }
    bool link(int x, int y) {
	x = root(x); y = root(y);
	if (x == y) return false;
	if (u[y] < u[x]) swap(x, y);
	u[x] += u[y]; u[y] = x; cc--;
	return true;
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int size(int x) { return -u[root(x)]; }
    int count() { return cc; }
};

int N, Q;

struct Edge {
    int x, y;
    LL c;
    int w;
    bool operator<(const Edge &o) const {
	return c < o.c;
    }
} E[200011];

void MAIN() {
    scanf("%d%d", &N, &Q);
    REP (i, Q) {
	scanf("%d%d%lld", &E[i].x, &E[i].y, &E[i].c);
    }

    sort(E, E+Q);
    UnionFind U(N);
    LL ans = 0;
    stack<Edge> s0, s1;
    LL cst = E[0].c;
    int idx = 0;
    while (1) {
	swap(s0, s1);
	while (idx < Q && E[idx].c == cst) {
	    s0.push(E[idx++]);
	}
	if (s0.empty()) break;
	while (!s0.empty()) {
	    Edge e = s0.top(); s0.pop();
	    e.w++;
	    if (!U.same(e.x, e.y)) {
		U.link(e.x, e.y);
//		eprintf("%d %d %lld %lld\n", e.x, e.y, e.c, cst);
		ans += cst;
		e.w = 0;
	    }
	    if (e.w <= 10) {
		e.x++;
		if (e.x >= N) e.x -= N;
		swap(e.x, e.y);
		e.c++;
		s1.push(e);
	    }
	}

	cst++;
    }

    printf("%lld\n", ans);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void MAIN()’:
./Main.cpp:83:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
                          ^
./Main.cpp:85:46: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &E[i].x, &E[i].y, &E[i].c);
                                              ^

Judge Result