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
AC × 3
AC × 36
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