CODE FESTIVAL 2016 Final

Submission #1177911

Source codeソースコード

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#define md double
#define LL long long
using namespace std;
const int N=5e5;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
int head[N],nxt[N],w[N],tot;
struct E{ int u,v,w; bool operator < (const E &b) const { return w<b.w; } }e[N];
inline void add(int k,int _w) { w[++tot]=_w,nxt[tot]=head[k],head[k]=tot; }
int fa[N];inline int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }
int main() {
	int n=gi(),m=gi(),i,a,b,c,k,t,ans=0;
	for (i=1;i<=m;i++) {
		a=gi(),b=gi(),c=gi();
		add(a,c+1);
		add(b,c+2);
		e[i]=(E){a,b,c};
		if (a) add(0,c+1+((n-a)<<1));
		if (b) add(0,c+2+((n-b)<<1));
	}
	for (k=0,t=1<<30;k<n;k++,t+=2) {
		for (i=head[k];i;i=nxt[i]) t=min(t,w[i]);
		e[++m]=(E){k,k+1==n?0:k+1,t};
	}
	sort(e+1,e+1+m);
	for (i=0;i<n;i++) fa[i]=i;
	for (i=1;i<=m;i++)
		if (find(e[i].u)!=find(e[i].v)) {
			ans+=e[i].w;
			fa[fa[e[i].u]]=e[i].v;
		}
	printf("%d\n",ans);
	return 0;
}

Submission

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

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt,sample-03.txt
all 0 / 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 2 ms 6400 KB
01-02.txt RE
01-03.txt RE
01-04.txt WA
01-05.txt WA
01-06.txt WA
01-07.txt WA
01-08.txt WA
01-09.txt WA
01-10.txt WA
01-11.txt RE
01-12.txt RE
01-13.txt RE
01-14.txt RE
01-15.txt RE
01-16.txt RE
01-17.txt RE
01-18.txt RE
01-19.txt WA
01-20.txt AC 17 ms 11520 KB
01-21.txt AC 34 ms 11520 KB
01-22.txt TLE
01-23.txt TLE
01-24.txt WA
01-25.txt TLE
01-26.txt WA
01-27.txt WA
01-28.txt WA
01-29.txt RE
01-30.txt RE
sample-01.txt AC 2 ms 6400 KB
sample-02.txt AC 2 ms 6400 KB
sample-03.txt AC 2 ms 6400 KB