CODE FESTIVAL 2016 Final

Submission #6352815

Source codeソースコード

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <cmath> 
#include <algorithm>
using namespace std; 
inline int gi() {
    register int data = 0, w = 1;
    register char ch = 0;
    while (!isdigit(ch) && ch != '-') ch = getchar(); 
    if (ch == '-') w = -1, ch = getchar(); 
    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); 
    return w * data; 
}
const int MAX_N = 2e5 + 5;
const int INF = 2e9; 
struct Edge { int u, v, w; } e[MAX_N << 1]; 
bool operator < (const Edge &l, const Edge &r) { return l.w < r.w; } 
int N, cnt, Q, ds[MAX_N]; 
int pa[MAX_N]; 
int getf(int x) { return x == pa[x] ? x : pa[x] = getf(pa[x]); }
long long ans = 0; 
int main () {
	N = gi(), Q = gi();
	for (int i = 1; i <= N; i++) ds[i] = INF; 
	while (Q--) { 
		int A = gi() + 1, B = gi() + 1, C = gi(); 
		e[++cnt] = (Edge){A, B, C};
		ds[A % N + 1] = min(ds[A % N + 1], C + 1); 
		ds[B % N + 1] = min(ds[B % N + 1], C + 2); 
	} 
	int pos = min_element(&ds[1], &ds[N + 1]) - ds; 
	for (int i = pos % N + 1, j = pos; i != pos; j = i, i = i % N + 1) ds[i] = min(ds[j] + 2, ds[i]); 
	for (int i = 2; i <= N; i++) e[++cnt] = (Edge){i - 1, i, ds[i]}; 
	e[++cnt] = (Edge){N, 1, ds[1]}; 
	sort(&e[1], &e[cnt + 1]);
	for (int i = 1; i <= N; i++) pa[i] = i; 
	for (int i = 1; i <= cnt; i++) {
		int u = getf(e[i].u), v = getf(e[i].v); 
		if (u == v) continue;
		ans += e[i].w, pa[u] = v; 
	} 
	printf("%lld\n", ans); 
    return 0; 
} 

Submission

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

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

./Main.cpp:9:5: warning: 'register' storage class specifier is deprecated and incompatible with C++1z [-Wdeprecated-register]
register int data = 0, w = 1;
^~~~~~~~~
./Main.cpp:9:5: warning: 'register' storage class specifier is deprecated and incompatible with C++1z [-Wdeprecated-register]
register int data = 0, w = 1;
^~~~~~~~~
./Main.cpp:10:5: warning: 'register' storage class specifier is deprecated and incompatible with C++1z [-Wdeprecated-register]
register char ch = 0;
^~~~~~~~~
3 warnings generated.

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 2304 KB
01-02.txt AC 42 ms 6400 KB
01-03.txt AC 74 ms 6784 KB
01-04.txt AC 13 ms 8832 KB
01-05.txt AC 11 ms 7552 KB
01-06.txt AC 13 ms 8064 KB
01-07.txt AC 15 ms 6912 KB
01-08.txt AC 16 ms 6656 KB
01-09.txt AC 20 ms 6528 KB
01-10.txt AC 45 ms 6528 KB
01-11.txt AC 62 ms 6400 KB
01-12.txt AC 73 ms 6528 KB
01-13.txt AC 73 ms 6528 KB
01-14.txt AC 75 ms 6528 KB
01-15.txt AC 76 ms 6528 KB
01-16.txt AC 74 ms 6528 KB
01-17.txt AC 74 ms 6528 KB
01-18.txt AC 46 ms 9600 KB
01-19.txt AC 14 ms 6784 KB
01-20.txt AC 17 ms 6528 KB
01-21.txt AC 30 ms 6528 KB
01-22.txt AC 53 ms 6528 KB
01-23.txt AC 53 ms 6528 KB
01-24.txt AC 13 ms 9600 KB
01-25.txt AC 56 ms 9600 KB
01-26.txt AC 14 ms 9216 KB
01-27.txt AC 18 ms 8064 KB
01-28.txt AC 46 ms 8064 KB
01-29.txt AC 52 ms 7296 KB
01-30.txt AC 63 ms 8064 KB
sample-01.txt AC 1 ms 2304 KB
sample-02.txt AC 1 ms 2304 KB
sample-03.txt AC 1 ms 2304 KB