Submission #2860343
Source Code Expand
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::sort;
using std::min;
const int MAXN=400010;
struct Edge {
int u,v,w;
friend bool operator<(Edge a,Edge b) {
return a.w<b.w;
}
}ed[MAXN];
int cnt=0;
inline void join(int x,int y,int z) {
ed[++cnt].u=x;
ed[cnt].v=y;
ed[cnt].w=z;
return;
}
int f[MAXN];
inline void init(int n) {
for(int i=0;i<=n;++i) {
f[i]=i;
}
}
int find(int x) {
return x==f[x]?x:(f[x]=find(f[x]));
}
int best[MAXN];
int main() {
memset(best,0x3f,sizeof(best));
int n,q;
scanf("%d%d",&n,&q);
int x,y,z;
for(int i=1;i<=q;++i) {
scanf("%d%d%d",&x,&y,&z);
join(x,y,z);
best[x]=min(best[x],z+1);
best[y]=min(best[y],z+2);
for(int i=0;i<n*2;++i) {
best[(i+1)%n]=min(best[(i+1)%n],best[i]+2); //n*2防止更新了n-1到0
}
}
for(int i=0;i<n;++i) {
if(best[i]!=0x3f3f3f3f) join(i,(i+1)%n,best[i]);
}
init(n);
sort(ed+1,ed+1+cnt);
long long ans=0;
for(int i=1;i<=cnt;++i) {
int a=find(ed[i].u),b=find(ed[i].v);
if(a!=b) {
ans+=ed[i].w;
f[a]=b;
}
}
printf("%lld",ans);
return 0;
}
Submission Info
Submission Time
2018-07-17 21:07:34+0900
Task
G - Zigzag MST
User
Sleepp
Language
C++ (GCC 5.4.1)
Score
0
Code Size
1125 Byte
Status
WA
Exec Time
2103 ms
Memory
8960 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:33: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:36:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&x,&y,&z);
^
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
2 ms
3712 KB
01-02.txt
AC
65 ms
5760 KB
01-03.txt
TLE
2103 ms
3712 KB
01-04.txt
WA
17 ms
8576 KB
01-05.txt
WA
14 ms
7424 KB
01-06.txt
AC
30 ms
7808 KB
01-07.txt
AC
156 ms
6656 KB
01-08.txt
AC
1448 ms
6400 KB
01-09.txt
TLE
2103 ms
3712 KB
01-10.txt
TLE
2103 ms
3712 KB
01-11.txt
TLE
2103 ms
3712 KB
01-12.txt
TLE
2103 ms
3712 KB
01-13.txt
TLE
2103 ms
3712 KB
01-14.txt
TLE
2103 ms
3712 KB
01-15.txt
TLE
2103 ms
3712 KB
01-16.txt
TLE
2103 ms
3712 KB
01-17.txt
TLE
2103 ms
3712 KB
01-18.txt
TLE
2103 ms
3712 KB
01-19.txt
AC
20 ms
6656 KB
01-20.txt
TLE
2103 ms
3712 KB
01-21.txt
TLE
2103 ms
3712 KB
01-22.txt
TLE
2103 ms
3712 KB
01-23.txt
TLE
2103 ms
3712 KB
01-24.txt
TLE
2103 ms
3712 KB
01-25.txt
TLE
2103 ms
3712 KB
01-26.txt
AC
22 ms
8960 KB
01-27.txt
TLE
2103 ms
3712 KB
01-28.txt
TLE
2103 ms
3712 KB
01-29.txt
TLE
2103 ms
3712 KB
01-30.txt
TLE
2103 ms
3712 KB
sample-01.txt
AC
2 ms
3712 KB
sample-02.txt
AC
2 ms
3712 KB
sample-03.txt
AC
2 ms
3712 KB