CODE FESTIVAL 2016 Final

Submission #5377235

Source codeソースコード

#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

Task問題 G - Zigzag MST
User nameユーザ名 n
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1300
Source lengthソースコード長 2882 Byte
File nameファイル名
Exec time実行時間 109 ms
Memory usageメモリ使用量 10752 KB

Compiler messageコンパイルメッセージ

./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);
^

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt,sample-03.txt
all 1300 / 1300 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,sample-01.txt,sample-02.txt,sample-03.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 1 ms 256 KB
01-02.txt AC 64 ms 4992 KB
01-03.txt AC 77 ms 5760 KB
01-04.txt AC 6 ms 1024 KB
01-05.txt AC 7 ms 1024 KB
01-06.txt AC 7 ms 1024 KB
01-07.txt AC 6 ms 1024 KB
01-08.txt AC 6 ms 1024 KB
01-09.txt AC 10 ms 1280 KB
01-10.txt AC 43 ms 5120 KB
01-11.txt AC 79 ms 5376 KB
01-12.txt AC 78 ms 5760 KB
01-13.txt AC 79 ms 5760 KB
01-14.txt AC 78 ms 5760 KB
01-15.txt AC 79 ms 5760 KB
01-16.txt AC 79 ms 5760 KB
01-17.txt AC 78 ms 5760 KB
01-18.txt AC 100 ms 10752 KB
01-19.txt AC 6 ms 1024 KB
01-20.txt AC 10 ms 1152 KB
01-21.txt AC 38 ms 3840 KB
01-22.txt AC 103 ms 10752 KB
01-23.txt AC 102 ms 10752 KB
01-24.txt AC 14 ms 1280 KB
01-25.txt AC 93 ms 5760 KB
01-26.txt AC 8 ms 1024 KB
01-27.txt AC 14 ms 1536 KB
01-28.txt AC 71 ms 8192 KB
01-29.txt AC 102 ms 10240 KB
01-30.txt AC 109 ms 10624 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB