Submission #4423332
Source Code Expand
#include<bits/stdc++.h>
#define int ll
using namespace std;typedef long long ll;
#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)
#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;++t)
#define ERP(t,a) for(register int t=head[a];t;t=e[t].nx)
#define midd register int mid=(l+r)>>1
#define TMP template < class ccf >
#define lef l,mid,pos<<1
#define rgt mid+1,r,pos<<1|1
#define pushup(pos) (seg[pos]=seg[pos<<1]+seg[pos<<1|1])
TMP inline ccf qr(ccf b){
register char c=getchar();register int q=1;register ccf x=0;
while(c<48||c>57)q=c==45?-1:q,c=getchar();
while(c>=48&&c<=57)x=x*10+c-48,c=getchar();
return q==-1?-x:x;}
TMP inline ccf Max(ccf a,ccf b){return a<b?b:a;}
TMP inline ccf Min(ccf a,ccf b){return a<b?a:b;}
TMP inline ccf Max(ccf a,ccf b,ccf c){return Max(a,Max(b,c));}
TMP inline ccf Min(ccf a,ccf b,ccf c){return Min(a,Min(b,c));}
TMP inline ccf READ(ccf* _arr,int _n){RP(t,1,_n)_arr[t]=qr((ccf)1);}
//----------------------template&IO---------------------------
const int maxn=200005;
struct E{
int fr,to,w;
inline bool operator < (E a){return w<a.w;}
}e[maxn<<1];
int cnt;
int r[maxn];
inline void add(int fr,int to,int w){
e[++cnt]=(E){fr,to,w};
}
inline int q(int x){
register int t=x,i=x,temp;
while(r[t]!=t) t=r[t];temp=t;
while(r[i]!=i) {temp=r[i];r[i]=t;i=temp;}
return t;
}
inline bool in(int x,int y){return not(q(x)^q(y));}
inline void j(int x,int y){r[q(x)]=q(y);}
int f[maxn];
int n,m;
signed main(){
n=qr(1LL);m=qr(1LL);
RP(t,0,n) r[t]=t;
register int t1,t2,t3;
RP(t,0,n+1) f[t]=1LL<<50;
RP(t,1,m){
t1=qr(1);
t2=qr(1);
t3=qr(1);
add(t1,t2,t3);
f[t1]=Min(f[t1],t3+1LL);
f[t2]=Min(f[t2],t3+2LL);
}
RP(t0,1,2) RP(t,0,n) f[t%n]=Min(f[t%n],f[(t-1+n)%n]+2LL);
RP(t,0,n) add(t%n,(t+1)%n,f[t%n]);
sort(e+1,e+cnt+1);ll ret=0;
RP(t,1,cnt){
if(not in(e[t].fr,e[t].to)){
ret+=(ll)e[t].w;
j(e[t].fr,e[t].to);
}
}
cout<<ret<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
luogu_bot2 |
Language |
C++ (GCC 5.4.1) |
Score |
1300 |
Code Size |
1999 Byte |
Status |
AC |
Exec Time |
90 ms |
Memory |
12800 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 |
2 ms |
2304 KB |
01-02.txt |
AC |
40 ms |
6400 KB |
01-03.txt |
AC |
85 ms |
12800 KB |
01-04.txt |
AC |
33 ms |
8448 KB |
01-05.txt |
AC |
25 ms |
8448 KB |
01-06.txt |
AC |
29 ms |
8448 KB |
01-07.txt |
AC |
28 ms |
8448 KB |
01-08.txt |
AC |
29 ms |
8448 KB |
01-09.txt |
AC |
33 ms |
8448 KB |
01-10.txt |
AC |
60 ms |
10496 KB |
01-11.txt |
AC |
69 ms |
9728 KB |
01-12.txt |
AC |
88 ms |
12672 KB |
01-13.txt |
AC |
87 ms |
12800 KB |
01-14.txt |
AC |
90 ms |
12800 KB |
01-15.txt |
AC |
88 ms |
12800 KB |
01-16.txt |
AC |
87 ms |
12800 KB |
01-17.txt |
AC |
87 ms |
12800 KB |
01-18.txt |
AC |
67 ms |
12800 KB |
01-19.txt |
AC |
27 ms |
8448 KB |
01-20.txt |
AC |
31 ms |
8448 KB |
01-21.txt |
AC |
47 ms |
10496 KB |
01-22.txt |
AC |
73 ms |
12800 KB |
01-23.txt |
AC |
74 ms |
12800 KB |
01-24.txt |
AC |
26 ms |
8448 KB |
01-25.txt |
AC |
89 ms |
12800 KB |
01-26.txt |
AC |
33 ms |
8448 KB |
01-27.txt |
AC |
35 ms |
8448 KB |
01-28.txt |
AC |
67 ms |
12544 KB |
01-29.txt |
AC |
67 ms |
11904 KB |
01-30.txt |
AC |
83 ms |
12800 KB |
sample-01.txt |
AC |
2 ms |
2304 KB |
sample-02.txt |
AC |
2 ms |
2304 KB |
sample-03.txt |
AC |
2 ms |
2304 KB |