Submission #4419594


Source Code Expand

#include<bits/stdc++.h>
namespace IO{
	const int maxn(1<<21|1);
	char ibuf[maxn],*iS,*iT,obuf[maxn],*oS=obuf,*oT=obuf+maxn-1,_c,_st[55];
	int _f,tp;
	char Getc(){return (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,maxn,stdin),(iS==iT?EOF:*iS++)):*iS++);}
	void Flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}
	void Putc(char x){*oS++=x;if(oS==oT)Flush();}
	template<class Int>void Input(Int &x){
		for(_f=0,_c=Getc();_c<'0'||_c>'9';_c=Getc())_f=_c=='-';
		for(x=0;_c<='9'&&_c>='0';_c=Getc())x=(x<<3)+(x<<1)+(_c^48);
		if(_f)x=-x;
	}
	template<class Int>void Print(Int x){
		if(!x)Putc('0');
		if(x<0)Putc('-'),x=-x;
		while(x)_st[++tp]=x%10+'0',x/=10;
		while(tp)Putc(_st[tp--]);
	}
}
using namespace IO;
using namespace std;
const int _=1e6+5;
int f[_],A[_],B[_],W[_],fa[_],n,m;
int cmp(int x,int y){return W[x]<W[y];}
vector<int>fz;int x,y=2e9;
int fi(int x){return fa[x]?fa[x]=fi(fa[x]):x;}
int main(){
	Input(n);Input(m);memset(f,63,sizeof(f));
	for(int i=1;i<=m;++i){
		Input(A[i]);Input(B[i]);Input(W[i]);++A[i];++B[i];
		f[A[i]]=min(f[A[i]],W[i]+1);f[B[i]]=min(f[B[i]],W[i]+2);
		if(f[A[i]]<y)x=A[i],y=f[x];
		if(f[B[i]]<y)x=B[i],y=f[x];
	}
	for(int i=x;i<=n;++i)f[i]=min(f[i],f[i-1]+2);f[1]=min(f[1],f[n]+2);
	for(int i=2;i<=x;++i)f[i]=min(f[i],f[i-1]+2);
	for(int i=1;i<=n;++i)A[++m]=i,B[m]=i%n+1,W[m]=f[i];
	for(int i=1;i<=m;++i)fz.push_back(i);
	sort(fz.begin(),fz.end(),cmp);
	long long ans=0;
	for(int i:fz){
		int fx=fi(A[i]),fy=fi(B[i]);
		if(fx!=fy)fa[fx]=fy,ans+=W[i];
	}
	cout<<ans<<endl;
}

Submission Info

Submission Time
Task G - Zigzag MST
User the_Despair_
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1499 Byte
Status AC
Exec Time 85 ms
Memory 27376 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 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 AC 4 ms 14592 KB
01-02.txt AC 41 ms 23032 KB
01-03.txt AC 72 ms 24560 KB
01-04.txt AC 38 ms 24692 KB
01-05.txt AC 25 ms 23540 KB
01-06.txt AC 30 ms 23924 KB
01-07.txt AC 25 ms 22772 KB
01-08.txt AC 25 ms 22516 KB
01-09.txt AC 29 ms 22516 KB
01-10.txt AC 50 ms 24052 KB
01-11.txt AC 59 ms 24052 KB
01-12.txt AC 72 ms 24304 KB
01-13.txt AC 72 ms 24304 KB
01-14.txt AC 72 ms 24304 KB
01-15.txt AC 75 ms 24304 KB
01-16.txt AC 72 ms 24304 KB
01-17.txt AC 72 ms 24304 KB
01-18.txt AC 47 ms 27376 KB
01-19.txt AC 25 ms 22772 KB
01-20.txt AC 30 ms 22388 KB
01-21.txt AC 40 ms 22644 KB
01-22.txt AC 55 ms 24304 KB
01-23.txt AC 55 ms 24304 KB
01-24.txt AC 24 ms 25588 KB
01-25.txt AC 85 ms 27376 KB
01-26.txt AC 36 ms 25076 KB
01-27.txt AC 34 ms 24052 KB
01-28.txt AC 50 ms 25584 KB
01-29.txt AC 54 ms 24560 KB
01-30.txt AC 67 ms 25840 KB
sample-01.txt AC 4 ms 14592 KB
sample-02.txt AC 4 ms 14592 KB
sample-03.txt AC 4 ms 14592 KB