Submission #4419161


Source Code Expand

Copy
#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 Info

Submission Time
Task G - Zigzag MST
User gzy_cjoier
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1591 Byte
Status
Exec Time 100 ms
Memory 6528 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1300 / 1300
Status
× 3
× 36
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
all 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
Case Name Status Exec Time Memory
01-01.txt 1 ms 1024 KB
01-02.txt 45 ms 3584 KB
01-03.txt 84 ms 6528 KB
01-04.txt 30 ms 4352 KB
01-05.txt 20 ms 4352 KB
01-06.txt 25 ms 4352 KB
01-07.txt 20 ms 4352 KB
01-08.txt 19 ms 4352 KB
01-09.txt 21 ms 4352 KB
01-10.txt 48 ms 6400 KB
01-11.txt 69 ms 6016 KB
01-12.txt 80 ms 6528 KB
01-13.txt 80 ms 6528 KB
01-14.txt 80 ms 6528 KB
01-15.txt 82 ms 6528 KB
01-16.txt 79 ms 6528 KB
01-17.txt 80 ms 6528 KB
01-18.txt 64 ms 6528 KB
01-19.txt 20 ms 4352 KB
01-20.txt 17 ms 4352 KB
01-21.txt 31 ms 6400 KB
01-22.txt 62 ms 6528 KB
01-23.txt 62 ms 6528 KB
01-24.txt 20 ms 4352 KB
01-25.txt 100 ms 6528 KB
01-26.txt 30 ms 4352 KB
01-27.txt 24 ms 4352 KB
01-28.txt 55 ms 6400 KB
01-29.txt 66 ms 6016 KB
01-30.txt 78 ms 6528 KB
sample-01.txt 1 ms 1024 KB
sample-02.txt 1 ms 1024 KB
sample-03.txt 1 ms 1024 KB