Submission #6398860


Source Code Expand

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int sum=0;
    char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)){
        sum=sum*10+(c^48);
        c=getchar();
    }
    return sum;
}
int const maxn=200005;
int const maxm=400005;
int n,q,cnt,ans,H[maxn],f[maxn],father[maxn];
struct Edge{
    int from,to,length;
}E[maxm];
inline void add(int a,int b,int c){
    E[++cnt]=(Edge){a,b,c};
    H[a]=cnt;
}
int find(int x){
    if(father[x]!=x) father[x]=find(father[x]);
    return father[x];
}
inline bool cmp(Edge x,Edge y){
    return x.length<y.length;
}
inline void kruskal(){
    sort(E+1,E+cnt+1,cmp);
    for(int i=1;i<=n;i++)
      father[i]=i;
    for(int i=1;i<=cnt;i++){
        int r1=find(E[i].from),r2=find(E[i].to);
        if(r1!=r2) father[r1]=r2,ans+=E[i].length;
    }
}
signed main(){
    n=read(),q=read();
    for(int i=1;i<=n;i++)
      f[i]=1e16;
    for(int i=1;i<=q;i++){
        int x=read()+1,y=read()+1,z=read();
        add(x,y,z);
        f[x]=min(f[x],z+1),f[y]=min(f[y],z+2);
    }
    //这个做法要记住的,它很巧妙地通过了断环为链,并且扫两遍,求出了环的前缀
    for(int i=1;i<=2*n-1;i++){
        int pre=(i%n==1)?n:((i-1)%n);
        f[(i-1)%n+1]=min(f[(i-1)%n+1],f[pre]+2);
    }
    for(int i=1;i<=n;i++)
      add(i,i%n+1,f[i]);
    kruskal();
    printf("%lld\n",ans);
    return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User wangzhijian
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1484 Byte
Status AC
Exec Time 134 ms
Memory 17408 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 4352 KB
01-02.txt AC 53 ms 10496 KB
01-03.txt AC 108 ms 14592 KB
01-04.txt AC 53 ms 14592 KB
01-05.txt AC 38 ms 13312 KB
01-06.txt AC 45 ms 13824 KB
01-07.txt AC 39 ms 12672 KB
01-08.txt AC 38 ms 12416 KB
01-09.txt AC 42 ms 12288 KB
01-10.txt AC 73 ms 14336 KB
01-11.txt AC 88 ms 13312 KB
01-12.txt AC 105 ms 14336 KB
01-13.txt AC 106 ms 14336 KB
01-14.txt AC 106 ms 14336 KB
01-15.txt AC 108 ms 14336 KB
01-16.txt AC 105 ms 14336 KB
01-17.txt AC 106 ms 14336 KB
01-18.txt AC 88 ms 17408 KB
01-19.txt AC 38 ms 12544 KB
01-20.txt AC 38 ms 12288 KB
01-21.txt AC 55 ms 12288 KB
01-22.txt AC 86 ms 14336 KB
01-23.txt AC 87 ms 14336 KB
01-24.txt AC 38 ms 15360 KB
01-25.txt AC 134 ms 17408 KB
01-26.txt AC 53 ms 14848 KB
01-27.txt AC 47 ms 13824 KB
01-28.txt AC 78 ms 15872 KB
01-29.txt AC 85 ms 14336 KB
01-30.txt AC 104 ms 15872 KB
sample-01.txt AC 2 ms 4352 KB
sample-02.txt AC 2 ms 4352 KB
sample-03.txt AC 2 ms 4352 KB