Submission #6769462
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF=1e9+7,MAXN=2e5+10,MAXM=4e5+10;
struct node {
int u,v;
LL w;
node() {
u=v=w;
}
node(int x,int y,LL z) {
u=x;
v=y;
w=z;
}
friend bool operator<(node x,node y) {
return x.w<y.w;
}
} e[MAXM];
int sz;
inline void add(int x,int y,LL z) {
e[++sz]=node(x,y,z);
}
int fa[MAXN];
int findset(int x) {
return fa[x]==x?x:fa[x]=findset(fa[x]);
}
int N,Q;
LL d[MAXN];
int main() {
scanf("%d%d",&N,&Q);
memset(d,0x3f,sizeof(d));
for(int i=1,ii,jj; i<=Q; i++) {
LL kk;
scanf("%d%d%lld",&ii,&jj,&kk);
add(ii,jj,kk);
d[ii]=min(d[ii],kk+1);
d[jj]=min(d[jj],kk+2);
}
for(int i=0; i<N; i++)
d[i]=min(d[i],d[(i+N-1)%N]+2);
for(int i=0; i<N; i++)
d[i]=min(d[i],d[(i+N-1)%N]+2);
for(int i=0; i<=N; i++)
add(i,(i+1)%N,d[i]);
sort(e+1,e+sz+1);
for(int i=1; i<N; i++)
fa[i]=i;
LL cnt=N-1,ans=0;
for(int i=1; i<=sz&&cnt; i++) {
int f1=findset(e[i].u),f2=findset(e[i].v);
if(f1!=f2) {
ans+=e[i].w;
fa[f1]=f2;
cnt--;
}
}
printf("%lld",ans);
return 0;
}
Submission Info
Submission Time
2019-08-08 17:36:15+0900
Task
G - Zigzag MST
User
guoshaoyang
Language
C++ (GCC 5.4.1)
Score
1300
Code Size
1128 Byte
Status
AC
Exec Time
93 ms
Memory
11136 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:31:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&N,&Q);
^
./Main.cpp:35:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld",&ii,&jj,&kk);
^
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
8320 KB
01-02.txt
AC
65 ms
8320 KB
01-03.txt
AC
93 ms
9088 KB
01-04.txt
AC
22 ms
11136 KB
01-05.txt
AC
14 ms
9856 KB
01-06.txt
AC
18 ms
10368 KB
01-07.txt
AC
17 ms
9216 KB
01-08.txt
AC
17 ms
8960 KB
01-09.txt
AC
21 ms
8832 KB
01-10.txt
AC
55 ms
8832 KB
01-11.txt
AC
82 ms
8704 KB
01-12.txt
AC
93 ms
8832 KB
01-13.txt
AC
93 ms
8832 KB
01-14.txt
AC
91 ms
8832 KB
01-15.txt
AC
93 ms
8832 KB
01-16.txt
AC
92 ms
8832 KB
01-17.txt
AC
91 ms
8832 KB
01-18.txt
AC
75 ms
8832 KB
01-19.txt
AC
16 ms
9216 KB
01-20.txt
AC
20 ms
8832 KB
01-21.txt
AC
41 ms
8832 KB
01-22.txt
AC
85 ms
8832 KB
01-23.txt
AC
84 ms
8832 KB
01-24.txt
AC
15 ms
8832 KB
01-25.txt
AC
92 ms
8832 KB
01-26.txt
AC
20 ms
8832 KB
01-27.txt
AC
23 ms
8832 KB
01-28.txt
AC
60 ms
8832 KB
01-29.txt
AC
80 ms
8832 KB
01-30.txt
AC
91 ms
8832 KB
sample-01.txt
AC
4 ms
8320 KB
sample-02.txt
AC
4 ms
8320 KB
sample-03.txt
AC
4 ms
8320 KB