Submission #1177913
Source Code Expand
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#define md double
#define LL long long
using namespace std;
const int N=1e6;
int gi() {
int w=0;bool q=1;char c=getchar();
while ((c<'0'||c>'9') && c!='-') c=getchar();
if (c=='-') q=0,c=getchar();
while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
return q? w:-w;
}
int head[N],nxt[N],w[N],tot;
struct E{ int u,v,w; bool operator < (const E &b) const { return w<b.w; } }e[N];
inline void add(int k,int _w) { w[++tot]=_w,nxt[tot]=head[k],head[k]=tot; }
int fa[N];inline int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }
int main() {
int n=gi(),m=gi(),i,a,b,c,k,t,ans=0;
for (i=1;i<=m;i++) {
a=gi(),b=gi(),c=gi();
add(a,c+1);
add(b,c+2);
e[i]=(E){a,b,c};
if (a) add(0,c+1+((n-a)<<1));
if (b) add(0,c+2+((n-b)<<1));
}
for (k=0,t=1<<30;k<n;k++,t+=2) {
for (i=head[k];i;i=nxt[i]) t=min(t,w[i]);
e[++m]=(E){k,k+1==n?0:k+1,t};
}
sort(e+1,e+1+m);
for (i=0;i<n;i++) fa[i]=i;
for (i=1;i<=m;i++)
if (find(e[i].u)!=find(e[i].v)) {
ans+=e[i].w;
fa[fa[e[i].u]]=e[i].v;
}
printf("%d\n",ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
laofu |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1208 Byte |
Status |
WA |
Exec Time |
82 ms |
Memory |
21376 KB |
Judge Result
Set Name |
sample |
all |
Score / Max Score |
0 / 0 |
0 / 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 |
3 ms |
8448 KB |
01-02.txt |
AC |
46 ms |
16640 KB |
01-03.txt |
WA |
80 ms |
19584 KB |
01-04.txt |
WA |
19 ms |
14720 KB |
01-05.txt |
WA |
12 ms |
13952 KB |
01-06.txt |
WA |
16 ms |
14208 KB |
01-07.txt |
WA |
14 ms |
13568 KB |
01-08.txt |
WA |
15 ms |
13440 KB |
01-09.txt |
WA |
19 ms |
13312 KB |
01-10.txt |
WA |
49 ms |
17408 KB |
01-11.txt |
WA |
73 ms |
17024 KB |
01-12.txt |
WA |
80 ms |
19456 KB |
01-13.txt |
WA |
80 ms |
19456 KB |
01-14.txt |
WA |
80 ms |
19456 KB |
01-15.txt |
WA |
82 ms |
19456 KB |
01-16.txt |
WA |
80 ms |
19456 KB |
01-17.txt |
WA |
80 ms |
19456 KB |
01-18.txt |
WA |
56 ms |
21376 KB |
01-19.txt |
WA |
14 ms |
13568 KB |
01-20.txt |
AC |
18 ms |
13312 KB |
01-21.txt |
AC |
34 ms |
15360 KB |
01-22.txt |
AC |
64 ms |
19456 KB |
01-23.txt |
AC |
63 ms |
19456 KB |
01-24.txt |
WA |
14 ms |
15232 KB |
01-25.txt |
WA |
76 ms |
21376 KB |
01-26.txt |
WA |
19 ms |
14848 KB |
01-27.txt |
WA |
21 ms |
14208 KB |
01-28.txt |
WA |
51 ms |
18304 KB |
01-29.txt |
WA |
65 ms |
17536 KB |
01-30.txt |
WA |
75 ms |
20352 KB |
sample-01.txt |
AC |
3 ms |
8448 KB |
sample-02.txt |
AC |
3 ms |
8448 KB |
sample-03.txt |
AC |
3 ms |
8448 KB |