Submission #1177909


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=5e5;
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],next[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,next[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=next[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 1211 Byte
Status CE

Compile Error

./Main.cpp: In function ‘void add(int, int)’:
./Main.cpp:21:45: error: reference to ‘next’ is ambiguous
 inline void add(int k,int _w) { w[++tot]=_w,next[tot]=head[k],head[k]=tot; }
                                             ^
./Main.cpp:19:13: note: candidates are: int next [500000]
 int head[N],next[N],w[N],tot;
             ^
In file included from /usr/include/c++/5/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/5/bits/char_traits.h:39,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/ostream:38,
                 from /usr/include/c++/5/iostream:39,
                 from ./Main.cpp:1:
/usr/include/c++/5/bits/stl_iterator_base_funcs.h:184:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:34:22: error: reference to ‘next’ is ambiguous
   for (i=...