Submission #3561929
Source Code Expand
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define RG register
#define LL long long
using namespace std;
const int N=2e6+10;
struct node{ int a,b; LL c; }pt[N];
int n,m,cnt,tot,fa[N];
LL minn[N],ans;
inline bool cmp(node a,node b){return a.c<b.c;}
inline int read(){
char ch=getchar(); int x=0, f=1;
while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0' && ch<='9'){x=x*10+ch-'0'; ch=getchar(); }
return x*f;}
inline LL mi(LL a,LL b){return a<b ? a : b;}
inline int f(int son){return fa[son]= fa[son]==son ? son : f(fa[son]);}
int main()
{
//freopen("Zigzag MST.in","r",stdin);
n=read(); m=read();
memset(minn,0x3f,sizeof minn);
for(RG int i=0;i<n;i++) fa[i]=i;
for(RG int i=1,a,b,c;i<=m;i++)
{
a=read()%n; b=read()%n; c=read();
pt[++cnt]={a,b,c};
minn[a]=mi(minn[a],c+1);
minn[b]=mi(minn[b],c+2);
}
for(RG int i=1;i<2*n;i++) minn[i%n]=mi(minn[i%n],minn[(i-1)%n]+2);
for(RG int i=0;i<n;i++) pt[++cnt]=(node){i%n,(i+1)%n,minn[i]};
sort(pt+1,pt+1+cnt,cmp);
for(RG int i=1;i<=cnt;i++)
{
int fx=f(pt[i].a), fy=f(pt[i].b);
if(fx==fy) continue;
fa[fx]=fy; ans+=pt[i].c;
if(++tot==n-1) return printf("%lld\n",ans), 0;
}
return 0;
}
Submission Info
Submission Time
2018-11-08 12:16:08+0900
Task
G - Zigzag MST
User
aoweiyin
Language
C++ (GCC 5.4.1)
Score
1300
Code Size
1250 Byte
Status
AC
Exec Time
108 ms
Memory
27136 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:29:19: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
pt[++cnt]={a,b,c};
^
./Main.cpp:29:12: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
pt[++cnt]={a,b,c};
^
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
6 ms
18688 KB
01-02.txt
AC
48 ms
20736 KB
01-03.txt
AC
92 ms
27136 KB
01-04.txt
AC
39 ms
24192 KB
01-05.txt
AC
28 ms
23424 KB
01-06.txt
AC
32 ms
23680 KB
01-07.txt
AC
28 ms
23040 KB
01-08.txt
AC
27 ms
22784 KB
01-09.txt
AC
32 ms
24832 KB
01-10.txt
AC
60 ms
24832 KB
01-11.txt
AC
76 ms
22784 KB
01-12.txt
AC
94 ms
26880 KB
01-13.txt
AC
94 ms
27008 KB
01-14.txt
AC
98 ms
26880 KB
01-15.txt
AC
94 ms
26880 KB
01-16.txt
AC
94 ms
26880 KB
01-17.txt
AC
91 ms
26880 KB
01-18.txt
AC
72 ms
26880 KB
01-19.txt
AC
28 ms
22912 KB
01-20.txt
AC
28 ms
22784 KB
01-21.txt
AC
46 ms
24832 KB
01-22.txt
AC
76 ms
26880 KB
01-23.txt
AC
77 ms
26880 KB
01-24.txt
AC
27 ms
24832 KB
01-25.txt
AC
108 ms
26880 KB
01-26.txt
AC
38 ms
22784 KB
01-27.txt
AC
35 ms
24832 KB
01-28.txt
AC
63 ms
24832 KB
01-29.txt
AC
75 ms
22784 KB
01-30.txt
AC
87 ms
26880 KB
sample-01.txt
AC
6 ms
18688 KB
sample-02.txt
AC
6 ms
18688 KB
sample-03.txt
AC
6 ms
18688 KB