Submission #1179678


Source Code Expand

// <mst.cpp> - Sat Mar 25 19:28:19 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=200010;
const int MAXM=400010;
const int INF=2e9;
struct edge{
    int x,y,w;
    bool operator <(const edge b) const{return w<b.w;}
}e[MAXM];
int a[MAXN],f[MAXN];
int gf(int x){if(f[x]!=f[f[x]])f[x]=gf(f[x]);return f[x];}
int main(){
    int n=gi(),m=gi();
    for(int i=0;i<n;i++)f[i]=i,a[i]=a[i+n]=INF;
    for(int i=1;i<=m;i++){
        e[i].x=gi();e[i].y=gi();e[i].w=gi();
        a[e[i].x]=min(a[e[i].x],e[i].w+1);
        a[e[i].y]=min(a[e[i].y],e[i].w+2);
    }
    for(int i=1;i<n<<1;i++)a[i]=min(a[i],a[i-1]+2);
    for(int i=0;i<n;i++)e[++m]=(edge){i,(i+1)%n,min(a[i],a[i+n])};
    sort(e+1,e+m+1);
    lol ans=0;
    for(int i=1;i<=m;i++){
        int fa=gf(e[i].x),fb=gf(e[i].y);
        if(fa!=fb)f[fa]=fb,ans+=e[i].w;
    }
    printf("%lld",ans);
    return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User XLightGod
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1514 Byte
Status WA
Exec Time 68 ms
Memory 7040 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 0 / 1300
Status
AC × 3
AC × 9
WA × 27
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 1 ms 256 KB
01-02.txt AC 37 ms 2816 KB
01-03.txt WA 65 ms 6528 KB
01-04.txt WA 14 ms 4352 KB
01-05.txt WA 15 ms 4480 KB
01-06.txt WA 14 ms 4608 KB
01-07.txt WA 14 ms 4864 KB
01-08.txt WA 15 ms 4992 KB
01-09.txt WA 17 ms 4992 KB
01-10.txt WA 38 ms 6400 KB
01-11.txt AC 61 ms 6016 KB
01-12.txt WA 66 ms 6528 KB
01-13.txt WA 66 ms 6528 KB
01-14.txt WA 68 ms 6528 KB
01-15.txt WA 65 ms 6528 KB
01-16.txt WA 66 ms 6528 KB
01-17.txt WA 65 ms 6528 KB
01-18.txt WA 49 ms 6528 KB
01-19.txt WA 15 ms 4992 KB
01-20.txt WA 13 ms 4352 KB
01-21.txt WA 20 ms 6400 KB
01-22.txt WA 51 ms 6528 KB
01-23.txt WA 51 ms 6528 KB
01-24.txt WA 17 ms 4736 KB
01-25.txt WA 61 ms 7040 KB
01-26.txt WA 14 ms 4352 KB
01-27.txt WA 19 ms 4352 KB
01-28.txt WA 42 ms 6400 KB
01-29.txt WA 56 ms 6784 KB
01-30.txt WA 60 ms 6528 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB