Submission #6769369
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,w;
node() {
u=v=w;
}
node(int x,int y,int 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,int 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;
int d[MAXN];
int main() {
scanf("%d%d",&N,&Q);
memset(d,0x3f,sizeof(d));
for(int i=1,ii,jj,kk; i<=Q; i++) {
scanf("%d%d%d",&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;
}
int 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("%d",ans);
return 0;
}
Submission Info
Submission Time
2019-08-08 17:29:02+0900
Task
G - Zigzag MST
User
guoshaoyang
Language
C++ (GCC 5.4.1)
Score
0
Code Size
1132 Byte
Status
WA
Exec Time
92 ms
Memory
8832 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:30: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:33:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&ii,&jj,&kk);
^
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
4 ms
5760 KB
01-02.txt
AC
61 ms
5760 KB
01-03.txt
WA
88 ms
6784 KB
01-04.txt
WA
22 ms
8832 KB
01-05.txt
WA
14 ms
7552 KB
01-06.txt
WA
18 ms
8064 KB
01-07.txt
WA
17 ms
6912 KB
01-08.txt
WA
17 ms
6656 KB
01-09.txt
WA
21 ms
6528 KB
01-10.txt
WA
53 ms
6528 KB
01-11.txt
WA
79 ms
6144 KB
01-12.txt
WA
88 ms
6528 KB
01-13.txt
WA
89 ms
6528 KB
01-14.txt
WA
87 ms
6528 KB
01-15.txt
WA
92 ms
6528 KB
01-16.txt
WA
87 ms
6528 KB
01-17.txt
WA
87 ms
6528 KB
01-18.txt
WA
71 ms
6528 KB
01-19.txt
WA
16 ms
6784 KB
01-20.txt
AC
20 ms
6528 KB
01-21.txt
AC
40 ms
6528 KB
01-22.txt
AC
79 ms
6528 KB
01-23.txt
AC
79 ms
6528 KB
01-24.txt
WA
15 ms
6528 KB
01-25.txt
WA
88 ms
6528 KB
01-26.txt
WA
20 ms
6528 KB
01-27.txt
WA
23 ms
6528 KB
01-28.txt
WA
57 ms
6528 KB
01-29.txt
WA
75 ms
6144 KB
01-30.txt
WA
86 ms
6528 KB
sample-01.txt
AC
4 ms
5760 KB
sample-02.txt
AC
4 ms
5760 KB
sample-03.txt
AC
4 ms
5760 KB