Submission #4173

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4173	2013-09-03T03:47:01 Z	cki86201	Race (IOI11_race)	C++	Compilation error	0 ms	0 KB

race

#include "race.h"
#include<string.h>
#include<algorithm>
using namespace std;

const int INF = 0x7fffffff;
const int MV = 200020;
typedef pair<int,int> P;

int st[MV],en[MV<<1],len[MV<<1],next[MV<<1];
int N,K;
int in,ans=INF;
int down[MV];
P M[1000010];
bool check[MV],cut[MV<<1];

void addedge(int s,int d,int l,int c)
{
	next[c]=st[s];
	st[s]=c;
	en[c]=d;
	len[c]=l;
}

int find_mid(int x)
{
	int i,r=x,upl=down[x]/2+1;
	for(;;){
		for(i=st[r];i!=-1;i=next[i]){
			if(cut[i]||down[en[i]]>down[r])continue;
			if(down[r]>=upl){r=en[i];break;}
		}
		if(i==-1)break;
	}
	return r;
}

void dfs(int x)
{
	check[x]=down[x]=1;
	for(int i=st[x];i!=-1;i=next[i]){
		if(!cut[i]&&!check[en[i]]){dfs(en[i]);down[x]+=down[en[i]];}
	}check[x]=0;
}

void find_(int x,int l,int d)
{
	if(l>K)return;
	if(M[K-l].second==in)ans=min(ans,d+M[K-l].first);
	for(int i=st[x];i!=-1;i=next[i]){
		if(cut[i]||down[en[i]]>down[x])continue;
		find_(en[i],l+len[i],d+1);
	}
}

void put_(int x,int l,int d)
{
	if(l>K)return;
	if(M[l].second!=in||M[l].first>=d)M[l].first=d,M[l].second=in;
	for(int i=st[x];i!=-1;i=next[i]){
		if(cut[i]||down[en[i]]>down[x])continue;
		put_(en[i],l+len[i],d+1);
	}
}

void solve(int x)
{
	++in;
	M[0]=P(0,in);
	int i,r=find_mid(x);
	dfs(r);
	for(i=st[r];i!=-1;i=next[i]){
		if(cut[i])continue;
		find_(en[i],len[i],1);
		put_(en[i],len[i],1);
	}
	for(i=st[r];i!=-1;i=next[i]){
		if(cut[i])continue;
		cut[i]=cut[i^1]=1;
		solve(en[i]);
	}
}

int best_path(int N_, int K_, int H[][2], int L[])
{
	int i;
	memset(st,-1,sizeof(st));
	K=K_,N=N_;
	for(i=0;i<N-1;i++){
		addedge(H[i][0],H[i][1],L[i],2*i);
		addedge(H[i][1],H[i][0],L[i],2*i+1);
	}
	dfs(0);
	solve(0);
	return ans==INF?-1:ans;
}

Compilation message

race.cpp: In function 'void addedge(int, int, int, int)':
race.cpp:19:2: error: reference to 'next' is ambiguous
  next[c]=st[s];
  ^~~~
race.cpp:10:33: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],len[MV<<1],next[MV<<1];
                                 ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from race.cpp:3:
/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
     ^~~~
race.cpp: In function 'int find_mid(int)':
race.cpp:29:23: error: reference to 'next' is ambiguous
   for(i=st[r];i!=-1;i=next[i]){
                       ^~~~
race.cpp:10:33: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],len[MV<<1],next[MV<<1];
                                 ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from race.cpp:3:
/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
     ^~~~
race.cpp: In function 'void dfs(int)':
race.cpp:40:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  check[x]=down[x]=1;
           ~~~~~~~^~
race.cpp:41:26: error: reference to 'next' is ambiguous
  for(int i=st[x];i!=-1;i=next[i]){
                          ^~~~
race.cpp:10:33: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],len[MV<<1],next[MV<<1];
                                 ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from race.cpp:3:
/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
     ^~~~
race.cpp: In function 'void find_(int, int, int)':
race.cpp:50:26: error: reference to 'next' is ambiguous
  for(int i=st[x];i!=-1;i=next[i]){
                          ^~~~
race.cpp:10:33: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],len[MV<<1],next[MV<<1];
                                 ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from race.cpp:3:
/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
     ^~~~
race.cpp: In function 'void put_(int, int, int)':
race.cpp:60:26: error: reference to 'next' is ambiguous
  for(int i=st[x];i!=-1;i=next[i]){
                          ^~~~
race.cpp:10:33: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],len[MV<<1],next[MV<<1];
                                 ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from race.cpp:3:
/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
     ^~~~
race.cpp: In function 'void solve(int)':
race.cpp:72:22: error: reference to 'next' is ambiguous
  for(i=st[r];i!=-1;i=next[i]){
                      ^~~~
race.cpp:10:33: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],len[MV<<1],next[MV<<1];
                                 ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from race.cpp:3:
/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
     ^~~~
race.cpp:77:22: error: reference to 'next' is ambiguous
  for(i=st[r];i!=-1;i=next[i]){
                      ^~~~
race.cpp:10:33: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],len[MV<<1],next[MV<<1];
                                 ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/algorithm:61,
                 from race.cpp:3:
/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
     ^~~~