CODE FESTIVAL 2016 Final

Submission #3435766

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=2e5+10,inf=0x3f3f3f3f;
int n,m,Min[maxn],fa[maxn];
struct Edge{
	int x,y,z;
	bool operator <(const Edge &rhs) const{
		return z<rhs.z;
	}
}E[maxn];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
int main(){
	memset(Min,inf,sizeof(Min));
	n=read(),m=read();
	REP(i,1,m){
		E[i].x=read(),E[i].y=read(),E[i].z=read();
		chkmin(Min[E[i].x],E[i].z+1);
		chkmin(Min[E[i].y],E[i].z+2);
	}
	int cur=inf;
	REP(i,0,2*n){
		cur+=2;
		chkmin(Min[i%n],cur);
		chkmin(cur,Min[i%n]);
	}
	REP(i,0,n-1) E[++m]=(Edge){i,(i+1)%n,Min[i]};
	sort(E+1,E+m+1);
	REP(i,0,n-1) fa[i]=i;
	ll ans=0;
	REP(i,1,m){
		int x=E[i].x,y=E[i].y,z=E[i].z;
		if(find(x)==find(y)) continue;
		fa[find(x)]=find(y);
		ans+=z;
	}
	printf("%lld\n",ans);
	return 0;
}

Submission

Task問題 G - Zigzag MST
User nameユーザ名 zhou888
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 RE
Score得点 0
Source lengthソースコード長 1605 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 1 ms 1024 KB
01-02.txt AC 41 ms 3328 KB
01-03.txt RE
01-04.txt AC 21 ms 6400 KB
01-05.txt AC 13 ms 5248 KB
01-06.txt AC 17 ms 5632 KB
01-07.txt WA
01-08.txt WA
01-09.txt WA
01-10.txt WA
01-11.txt AC 65 ms 4096 KB
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 AC 16 ms 4480 KB
01-20.txt WA
01-21.txt WA
01-22.txt RE
01-23.txt RE
01-24.txt WA
01-25.txt RE
01-26.txt AC 21 ms 6784 KB
01-27.txt WA
01-28.txt WA
01-29.txt WA
01-30.txt RE
sample-01.txt AC 1 ms 1024 KB
sample-02.txt AC 1 ms 1024 KB
sample-03.txt AC 1 ms 1024 KB