Submission #1177913


Source Code Expand

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#define md double
#define LL long long
using namespace std;
const int N=1e6;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
int head[N],nxt[N],w[N],tot;
struct E{ int u,v,w; bool operator < (const E &b) const { return w<b.w; } }e[N];
inline void add(int k,int _w) { w[++tot]=_w,nxt[tot]=head[k],head[k]=tot; }
int fa[N];inline int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }
int main() {
	int n=gi(),m=gi(),i,a,b,c,k,t,ans=0;
	for (i=1;i<=m;i++) {
		a=gi(),b=gi(),c=gi();
		add(a,c+1);
		add(b,c+2);
		e[i]=(E){a,b,c};
		if (a) add(0,c+1+((n-a)<<1));
		if (b) add(0,c+2+((n-b)<<1));
	}
	for (k=0,t=1<<30;k<n;k++,t+=2) {
		for (i=head[k];i;i=nxt[i]) t=min(t,w[i]);
		e[++m]=(E){k,k+1==n?0:k+1,t};
	}
	sort(e+1,e+1+m);
	for (i=0;i<n;i++) fa[i]=i;
	for (i=1;i<=m;i++)
		if (find(e[i].u)!=find(e[i].v)) {
			ans+=e[i].w;
			fa[fa[e[i].u]]=e[i].v;
		}
	printf("%d\n",ans);
	return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User laofu
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1208 Byte
Status WA
Exec Time 82 ms
Memory 21376 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 0 / 1300
Status
AC × 3
AC × 12
WA × 24
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 3 ms 8448 KB
01-02.txt AC 46 ms 16640 KB
01-03.txt WA 80 ms 19584 KB
01-04.txt WA 19 ms 14720 KB
01-05.txt WA 12 ms 13952 KB
01-06.txt WA 16 ms 14208 KB
01-07.txt WA 14 ms 13568 KB
01-08.txt WA 15 ms 13440 KB
01-09.txt WA 19 ms 13312 KB
01-10.txt WA 49 ms 17408 KB
01-11.txt WA 73 ms 17024 KB
01-12.txt WA 80 ms 19456 KB
01-13.txt WA 80 ms 19456 KB
01-14.txt WA 80 ms 19456 KB
01-15.txt WA 82 ms 19456 KB
01-16.txt WA 80 ms 19456 KB
01-17.txt WA 80 ms 19456 KB
01-18.txt WA 56 ms 21376 KB
01-19.txt WA 14 ms 13568 KB
01-20.txt AC 18 ms 13312 KB
01-21.txt AC 34 ms 15360 KB
01-22.txt AC 64 ms 19456 KB
01-23.txt AC 63 ms 19456 KB
01-24.txt WA 14 ms 15232 KB
01-25.txt WA 76 ms 21376 KB
01-26.txt WA 19 ms 14848 KB
01-27.txt WA 21 ms 14208 KB
01-28.txt WA 51 ms 18304 KB
01-29.txt WA 65 ms 17536 KB
01-30.txt WA 75 ms 20352 KB
sample-01.txt AC 3 ms 8448 KB
sample-02.txt AC 3 ms 8448 KB
sample-03.txt AC 3 ms 8448 KB