Submission #14087

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
14087	2015-04-28T12:23:03 Z	shuuna	Beads and wires (APIO14_beads)	C++	Compilation error	0 ms	0 KB

beads

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 200010
#define maxm 400010
using namespace std;
typedef long long LL;
int n,down[maxn],up[maxn],val[maxn],father[maxn];
int nEdge=1,to[maxm],next[maxm],len[maxm],start[maxn];
void make(int a,int b,int c)
{
	++nEdge,to[nEdge]=b,next[nEdge]=start[a],start[a]=nEdge,len[nEdge]=c;
}
void read()
{
	scanf("%d",&n);
	for(int i=2,a,b,c;i<=n;++i)
	{
		scanf("%d %d %d",&a,&b,&c);
		make(a,b,c),make(b,a,c);
	}
}
void BFS(int p)
{
	static int queue[maxn],in[maxn];
	int front=0,rear=1;
	queue[rear]=p,father[p]=0;
	while(front<rear)
	{
		int p=queue[++front];
		for(int i=start[p];i;i=next[i])
			if(to[i]!=father[p])
			{
				queue[++rear]=to[i];
				father[to[i]]=p;
				in[to[i]]=len[i];
			}
	}
	for(int i=n;i>=1;--i)
	{
		int p=queue[i],&ans=down[p];
		for(int j=start[p];j;j=next[j])
			if(to[j]!=father[p])
			{
				int q=to[j],tmp=down[q];
				for(int k=start[q];k;k=next[k])
					if(to[k]!=p)
						tmp=max(tmp,down[q]-val[to[k]]+down[to[k]]+len[j]+len[k]);
				ans+=tmp,val[q]=tmp;
			}
	}
	for(int i=1;i<=n;++i)
	{
		int p=queue[i],max1=-1<<30,id=0,max2=-1<<30,v1=0;
		if(father[p])
			v1=up[father[p]]+down[father[p]]-val[p]+down[p];
		for(int j=start[p];j;j=next[j])
			if(to[j]!=father[p])
			{
				int q=to[j],v=down[q]+len[j]-val[q];
				up[q]=up[p]+down[p]-val[q];
				if(father[p])
					up[q]=max(up[q],v1-val[to[j]]+len[j]+in[p]);
				if(max1<=v)
					max2=max1,max1=v,id=j;
				else if(max2<=v)
					max2=v;
			}
		for(int j=start[p];j;j=next[j])
			if(to[j]!=father[p])
			{
				int q=to[j];
				if(j==id)
					up[q]=max(up[q],up[p]+down[p]-val[q]+max2+len[j]);
				else
					up[q]=max(up[q],up[p]+down[p]-val[q]+max1+len[j]);
			}
	}
}
int work()
{
	int ans=0;
	BFS(1);
	for(int i=1;i<=n;++i)
		ans=max(ans,up[i]+down[i]);
	return ans;
}
int main()
{
	//freopen("beads.in","r",stdin);
	//freopen("beads.out","w",stdout);
	read();
	printf("%d\n",work());
	//fclose(stdin);
	//fclose(stdout);
	//system("pause");
	return 0;
}

Compilation message

beads.cpp: In function 'void make(int, int, int)':
beads.cpp:14:22: error: reference to 'next' is ambiguous
  ++nEdge,to[nEdge]=b,next[nEdge]=start[a],start[a]=nEdge,len[nEdge]=c;
                      ^~~~
beads.cpp:11:22: note: candidates are: int next [400010]
 int nEdge=1,to[maxm],next[maxm],len[maxm],start[maxn];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from beads.cpp:5:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
beads.cpp: In function 'void BFS(int)':
beads.cpp:33:26: error: reference to 'next' is ambiguous
   for(int i=start[p];i;i=next[i])
                          ^~~~
beads.cpp:11:22: note: candidates are: int next [400010]
 int nEdge=1,to[maxm],next[maxm],len[maxm],start[maxn];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from beads.cpp:5:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
beads.cpp:44:26: error: reference to 'next' is ambiguous
   for(int j=start[p];j;j=next[j])
                          ^~~~
beads.cpp:11:22: note: candidates are: int next [400010]
 int nEdge=1,to[maxm],next[maxm],len[maxm],start[maxn];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from beads.cpp:5:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
beads.cpp:48:28: error: reference to 'next' is ambiguous
     for(int k=start[q];k;k=next[k])
                            ^~~~
beads.cpp:11:22: note: candidates are: int next [400010]
 int nEdge=1,to[maxm],next[maxm],len[maxm],start[maxn];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from beads.cpp:5:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
beads.cpp:59:26: error: reference to 'next' is ambiguous
   for(int j=start[p];j;j=next[j])
                          ^~~~
beads.cpp:11:22: note: candidates are: int next [400010]
 int nEdge=1,to[maxm],next[maxm],len[maxm],start[maxn];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from beads.cpp:5:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
beads.cpp:71:26: error: reference to 'next' is ambiguous
   for(int j=start[p];j;j=next[j])
                          ^~~~
beads.cpp:11:22: note: candidates are: int next [400010]
 int nEdge=1,to[maxm],next[maxm],len[maxm],start[maxn];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from beads.cpp:5:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
beads.cpp: In function 'void read()':
beads.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~