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 |
|
|
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 |