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 |
|
|
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 |