Submission #4420409
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#define rg register
#define gc getchar()
#define rp(i,x,y) for(rg int i=x;i<=y;++i)
const int N=200000+10;
int n,q,fa[N];
ll mn[N<<1],as;
struct ed{int fr,to;ll wei;};
vector<ed>edge;
il int read()
{
rg char ch=gc;rg int x=0;rg bool y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il ll readl()
{
rg char ch=gc;rg ll x=0;rg bool y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il bool cmp(ed x,ed y){return x.wei<y.wei;}
il int fd(int x){return fa[x]==x?x:fa[x]=fd(fa[x]);}
int main()
{
n=read();q=read();memset(mn,127/3,sizeof(mn));
while(q--){int a=read()%n+1,b=read()%n+1;ll c=readl();mn[a]=min(mn[a],c+1);mn[b]=min(mn[b],c+2);edge.push_back((ed){a,b,c});}
rp(i,1,n<<1)mn[i]=min(mn[i],mn[i-1]+2);rp(i,1,n)edge.push_back((ed){i,i%n+1,min(mn[i],mn[i+n])});sort(edge.begin(),edge.end(),cmp);
rp(i,1,n)fa[i]=i;int sz=edge.size();rp(i,0,sz-1){int fafr=fd(edge[i].fr),fato=fd(edge[i].to);if(fafr^fato)as+=edge[i].wei,fa[fafr]=fato;}
printf("%lld\n",as);
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
luogu_bot3 |
Language |
C++ (GCC 5.4.1) |
Score |
1300 |
Code Size |
1306 Byte |
Status |
AC |
Exec Time |
112 ms |
Memory |
14056 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 |
2 ms |
3328 KB |
01-02.txt |
AC |
51 ms |
9584 KB |
01-03.txt |
AC |
93 ms |
12140 KB |
01-04.txt |
AC |
38 ms |
9068 KB |
01-05.txt |
AC |
26 ms |
8044 KB |
01-06.txt |
AC |
31 ms |
8300 KB |
01-07.txt |
AC |
27 ms |
9584 KB |
01-08.txt |
AC |
26 ms |
8432 KB |
01-09.txt |
AC |
31 ms |
9328 KB |
01-10.txt |
AC |
61 ms |
13548 KB |
01-11.txt |
AC |
78 ms |
12396 KB |
01-12.txt |
AC |
93 ms |
13036 KB |
01-13.txt |
AC |
94 ms |
12828 KB |
01-14.txt |
AC |
93 ms |
12524 KB |
01-15.txt |
AC |
95 ms |
12524 KB |
01-16.txt |
AC |
92 ms |
12908 KB |
01-17.txt |
AC |
94 ms |
13164 KB |
01-18.txt |
AC |
75 ms |
14056 KB |
01-19.txt |
AC |
26 ms |
8304 KB |
01-20.txt |
AC |
27 ms |
8944 KB |
01-21.txt |
AC |
42 ms |
8944 KB |
01-22.txt |
AC |
73 ms |
12908 KB |
01-23.txt |
AC |
73 ms |
13420 KB |
01-24.txt |
AC |
27 ms |
9452 KB |
01-25.txt |
AC |
112 ms |
13288 KB |
01-26.txt |
AC |
37 ms |
8940 KB |
01-27.txt |
AC |
34 ms |
8944 KB |
01-28.txt |
AC |
65 ms |
12268 KB |
01-29.txt |
AC |
78 ms |
13164 KB |
01-30.txt |
AC |
89 ms |
12780 KB |
sample-01.txt |
AC |
3 ms |
3328 KB |
sample-02.txt |
AC |
3 ms |
3328 KB |
sample-03.txt |
AC |
2 ms |
3328 KB |