Submission #3524358
Source Code Expand
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long long ll;
typedef double dd;
#define For(i,j,k) for (int i=(int)j;i<=(int)k;++i)
#define Forr(i,j,k) for (int i=(int)j;i>=(int)k;--i)
#define Set(a,p) memset(a,p,sizeof(a))
using namespace std;
template<typename T>bool chkmax(T &a,T b) { return a<b?a=b,1:0; }
template<typename T>bool chkmin(T &a,T b) { return a>b?a=b,1:0; }
const int maxn=2e6+1e2;
const int inf=0x3f3f3f3f;
struct Edge {
int from,to,dis;
bool operator < (const Edge &aa) const {
return dis<aa.dis;
}
}e[maxn];
int n,m;
int tot;
ll Ans;
int fa[maxn],val[maxn];
inline int read() {
int x=0,p=1;
char c=getchar();
while (!isdigit(c)) { if (c=='-') p=-1; c=getchar();}
while (isdigit(c)) { x=(x<<1)+(x<<3)+(c-'0'); c=getchar();}
return x*p;
}
inline void add(int u,int v,int w) {
e[++tot]=(Edge){u,v,w};
}
int find(int x) {
if (x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
int main() {
n=read(); m=read();
For (i,0,n) fa[i]=i; Set(val,inf);
while (m--) {
int u=read(),v=read(),w=read(); u%=n; v%=n;
chkmin(val[u],w+1); chkmin(val[v],w+2);
add(u,v,w);
}
For (i,1,n<<1) chkmin(val[i%n],val[(i-1)%n]+2);
For (i,0,n-1) add(i,(i+1)%n,val[i]);
sort(e+1,e+tot+1);
For (i,1,tot) {
int u=e[i].from,v=e[i].to;
u=find(u); v=find(v);
if (u!=v) {
Ans+=1ll*e[i].dis; fa[u]=v;
}
}
printf("%lld\n",Ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
Wuweizheng |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
1478 Byte |
Status |
AC |
Exec Time |
84 ms |
Memory |
19712 KB |
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 |
10496 KB |
01-02.txt |
AC |
42 ms |
12544 KB |
01-03.txt |
AC |
78 ms |
16896 KB |
01-04.txt |
AC |
23 ms |
16896 KB |
01-05.txt |
AC |
16 ms |
15616 KB |
01-06.txt |
AC |
19 ms |
16128 KB |
01-07.txt |
AC |
18 ms |
14976 KB |
01-08.txt |
AC |
18 ms |
14720 KB |
01-09.txt |
AC |
23 ms |
14592 KB |
01-10.txt |
AC |
49 ms |
16640 KB |
01-11.txt |
AC |
67 ms |
16640 KB |
01-12.txt |
AC |
79 ms |
16640 KB |
01-13.txt |
AC |
79 ms |
16640 KB |
01-14.txt |
AC |
81 ms |
16640 KB |
01-15.txt |
AC |
84 ms |
16640 KB |
01-16.txt |
AC |
78 ms |
16640 KB |
01-17.txt |
AC |
78 ms |
16640 KB |
01-18.txt |
AC |
56 ms |
19712 KB |
01-19.txt |
AC |
17 ms |
14976 KB |
01-20.txt |
AC |
21 ms |
14592 KB |
01-21.txt |
AC |
37 ms |
16640 KB |
01-22.txt |
AC |
62 ms |
16640 KB |
01-23.txt |
AC |
62 ms |
16640 KB |
01-24.txt |
AC |
18 ms |
17664 KB |
01-25.txt |
AC |
76 ms |
19712 KB |
01-26.txt |
AC |
23 ms |
17152 KB |
01-27.txt |
AC |
25 ms |
16128 KB |
01-28.txt |
AC |
53 ms |
18176 KB |
01-29.txt |
AC |
62 ms |
17536 KB |
01-30.txt |
AC |
74 ms |
18176 KB |
sample-01.txt |
AC |
4 ms |
10496 KB |
sample-02.txt |
AC |
4 ms |
10496 KB |
sample-03.txt |
AC |
4 ms |
10496 KB |