Submission #4145

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4145	2013-09-02T11:02:52 Z	cki86201	Race (IOI11_race)	C++	Compilation error	0 ms	0 KB

race

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

const int MV = 200020;
const int INF = 0x7fffffff;

int st[MV],en[MV<<1],next[MV<<1],len[MV<<1];
bool cut[MV<<1];
int N,K;
int ans = INF;
bool check[MV];
bool vis[MV];
int down[MV];
map <int,int> M;

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

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

void dfs_ans(int x,int l,int d)
{
	if(l>K)return;
	if(M.find(K-l)!=M.end())ans=min(ans,M[K-l]+d);
	for(int i=st[x];i!=-1;i=next[i]){
		if(!cut[i]&&down[en[i]]<down[x])dfs_ans(en[i],l+len[i],d+1);
	}
}

void dfs_map(int x,int l,int d)
{
	if(l>K)return;
	if(M.find(l)!=M.end())M[l]=min(M[l],d);
	else M[l]=d;
	for(int i=st[x];i!=-1;i=next[i]){
		if(!cut[i]&&down[en[i]]<down[x])dfs_map(en[i],l+len[i],d+1);
	}
}

void solve(int x)
{
	vis[x]=1;
	int r=x, upl=down[x]/2;
	for(;;){
		int i,tmp=r;
		for(i=st[r];i!=-1;i=next[i]){
			if(down[en[i]]>down[r])continue;
			if(down[en[i]]<=upl+1)break;
			else{r=en[i];break;}
		}
		if(tmp==r)break;
	}
	int i;
	dfs(r);
	M.clear();
	M[0]=0;
	for(i=st[r];i!=-1;i=next[i]){
		if(vis[en[i]])continue;
		dfs_ans(en[i],len[i],1);
		dfs_map(en[i],len[i],1);
		cut[i]=cut[i^1]=1;
	}
	for(i=st[r];i!=-1;i=next[i]){
		if(!vis[en[i]])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:21:2: error: reference to 'next' is ambiguous
  next[c]=st[s];
  ^~~~
race.cpp:10:22: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],next[MV<<1],len[MV<<1];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/stl_tree.h:63,
                 from /usr/include/c++/7/map:60,
                 from race.cpp:2:
/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 dfs(int)':
race.cpp:31:22: error: reference to 'next' is ambiguous
  for(i=st[x];i!=-1;i=next[i]){
                      ^~~~
race.cpp:10:22: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],next[MV<<1],len[MV<<1];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/stl_tree.h:63,
                 from /usr/include/c++/7/map:60,
                 from race.cpp:2:
/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_ans(int, int, int)':
race.cpp:42:26: error: reference to 'next' is ambiguous
  for(int i=st[x];i!=-1;i=next[i]){
                          ^~~~
race.cpp:10:22: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],next[MV<<1],len[MV<<1];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/stl_tree.h:63,
                 from /usr/include/c++/7/map:60,
                 from race.cpp:2:
/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_map(int, int, int)':
race.cpp:52:26: error: reference to 'next' is ambiguous
  for(int i=st[x];i!=-1;i=next[i]){
                          ^~~~
race.cpp:10:22: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],next[MV<<1],len[MV<<1];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/stl_tree.h:63,
                 from /usr/include/c++/7/map:60,
                 from race.cpp:2:
/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:63:23: error: reference to 'next' is ambiguous
   for(i=st[r];i!=-1;i=next[i]){
                       ^~~~
race.cpp:10:22: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],next[MV<<1],len[MV<<1];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/stl_tree.h:63,
                 from /usr/include/c++/7/map:60,
                 from race.cpp:2:
/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:74:22: error: reference to 'next' is ambiguous
  for(i=st[r];i!=-1;i=next[i]){
                      ^~~~
race.cpp:10:22: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],next[MV<<1],len[MV<<1];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/stl_tree.h:63,
                 from /usr/include/c++/7/map:60,
                 from race.cpp:2:
/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:80:22: error: reference to 'next' is ambiguous
  for(i=st[r];i!=-1;i=next[i]){
                      ^~~~
race.cpp:10:22: note: candidates are: int next [400040]
 int st[MV],en[MV<<1],next[MV<<1],len[MV<<1];
                      ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/stl_tree.h:63,
                 from /usr/include/c++/7/map:60,
                 from race.cpp:2:
/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
     ^~~~