CODE FESTIVAL 2016 Final

Submission #4419161

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
inline int read()
{
	int sum=0,p=1;char ch=getchar();
	while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
	if(ch=='-')p=-1,ch=getchar();
	while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
	return sum*p;
}

const int maxn=2e5+20;
const int inf=0x3f3f3f3f;

struct Edge {
	int u,v,w;
};
Edge E[maxn<<1];
int m;

int f[maxn];

int n,q;

inline void init()
{
	n=read();q=read();
	memset(f,inf,sizeof(f));
	REP(i,1,q)
	{
		int u=read(),v=read(),c=read();
		E[++m]=(Edge){u,v,c};
		chkmin(f[u],c+1);
		chkmin(f[v],c+2);
	}
	REP(i,0,n-1)chkmin(f[i+1<n?i+1:0],f[i]+2);
	REP(i,0,n-1)chkmin(f[i+1<n?i+1:0],f[i]+2);
	REP(i,0,n-1)E[++m]=(Edge){i,i+1<n?i+1:0,f[i]};
}

inline bool cmp(Edge a,Edge b){ return a.w<b.w;}
int fa[maxn];
int fin(int x){ return x==fa[x]?x:fa[x]=fin(fa[x]);}
inline void merge(int x,int y){ x=fin(x);y=fin(y); fa[y]=x;}

inline void doing()
{
	REP(i,1,n)fa[i]=i;
	sort(E+1,E+m+1,cmp);
	ll ans=0;
	REP(i,1,m)
	{
		int u=E[i].u,v=E[i].v;
		if(fin(u)==fin(v))continue;
		merge(u,v);
		ans+=E[i].w;
	}
	printf("%lld\n",ans);
}

int main()
{
	init();
	doing();
	return 0;
}

Submission

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

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 1024 KB
01-02.txt AC 45 ms 3584 KB
01-03.txt AC 84 ms 6528 KB
01-04.txt AC 30 ms 4352 KB
01-05.txt AC 20 ms 4352 KB
01-06.txt AC 25 ms 4352 KB
01-07.txt AC 20 ms 4352 KB
01-08.txt AC 19 ms 4352 KB
01-09.txt AC 21 ms 4352 KB
01-10.txt AC 48 ms 6400 KB
01-11.txt AC 69 ms 6016 KB
01-12.txt AC 80 ms 6528 KB
01-13.txt AC 80 ms 6528 KB
01-14.txt AC 80 ms 6528 KB
01-15.txt AC 82 ms 6528 KB
01-16.txt AC 79 ms 6528 KB
01-17.txt AC 80 ms 6528 KB
01-18.txt AC 64 ms 6528 KB
01-19.txt AC 20 ms 4352 KB
01-20.txt AC 17 ms 4352 KB
01-21.txt AC 31 ms 6400 KB
01-22.txt AC 62 ms 6528 KB
01-23.txt AC 62 ms 6528 KB
01-24.txt AC 20 ms 4352 KB
01-25.txt AC 100 ms 6528 KB
01-26.txt AC 30 ms 4352 KB
01-27.txt AC 24 ms 4352 KB
01-28.txt AC 55 ms 6400 KB
01-29.txt AC 66 ms 6016 KB
01-30.txt AC 78 ms 6528 KB
sample-01.txt AC 1 ms 1024 KB
sample-02.txt AC 1 ms 1024 KB
sample-03.txt AC 1 ms 1024 KB