Submission #598375

#	Time	Username	Problem	Language	Result	Execution time	Memory
598375		ono_de206	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include "race.h"
 
 
#include<bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define ff first
#define ss second
#define in insert
 
const int mxn=2e5+10;
vector<pair<int,int> > g[mxn];
int ans=-1,n,k,vis[mxn],sub[mxn],next,mx;
int cn[1000000];
 
void dfs(int to,int fr)
{
	sub[to]=1;
	for(auto &x : g[to])
	{
		if(x.ff==fr || vis[x.ff]) continue;
		dfs(x.ff,to);
		sub[to]+=sub[x.ff];
	}
}
 
void get_cen(int to,int fr,int sz)
{
	int lomx=sz-sub[to];
	for(auto &x : g[to])
	{
		if(x.ff==fr || vis[x.ff]) continue;
		get_cen(x.ff,to,sz);
		lomx=max(lomx,sub[x.ff]);
	}
	if(lomx<mx)
	{
		mx=lomx;
		next=to;
	}
}
 
void up(int tmp,int cnt)
{
	if(tmp==k) 
	{
		if(ans==-1) ans=cnt;
		else ans=min(ans,cnt);
	}
	else
	{
		if(cn[k-tmp]) 
		{
			if(ans==-1) ans=cnt+cn[k-tmp];
			else ans=min(ans,cnt+cn[k-tmp]);
		}
	}
}
 
void dfs2(int to,int fr,int tmp,int cnt)
{
	if(tmp>k) return;
	up(tmp,cnt);
	for(auto &x : g[to])
	{
		if(x.ff==fr || vis[x.ff]) continue;
		dfs2(x.ff,to,tmp+x.ss,cnt+1);
	}
}
 
void upd(int to,int fr,int tmp,int cnt)
{
	if(tmp>=k) return;
	cn[tmp]=(cn[tmp]==0 ? cnt : min(cn[tmp],cnt));
	for(auto x : g[to])
	{
		if(x.ff==fr || vis[x.ff]) continue;
		upd(x.ff,to,tmp+x.ss,cnt+1);
	}
}
 
void solve(int id)
{
	dfs(id,-1);
	if(sub[id]<=1) return;
	mx=sub[id];
	get_cen(id,-1,sub[id]);
	id=next;
	for(auto &x : g[id])
	{
		if(vis[x.ff]) continue;
		dfs2(x.ff,id,x.ss,1);
		upd(x.ff,id,x.ss,1);
	}
	vis[id]=1;
	memset(cn,0,sizeof(cn));
	for(auto &x : g[id])
	{
		if(vis[x.ff]) continue;
		solve(x.ff);
	}
}
 
int best_path(int N, int K, int h[][2], int l[])
{
	n=N;
	k=K;
	memset(vis,0,sizeof(vis));
	for(int i=0; i<N-1; i++)
	{
		g[h[i][0]].pb({h[i][1],l[i]});
		g[h[i][1]].pb({h[i][0],l[i]});
	}
	solve(0);
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void get_cen(int, int, int)':
race.cpp:40:3: error: reference to 'next' is ambiguous
   40 |   next=to;
      |   ^~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:66,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from race.cpp:4:
/usr/include/c++/10/bits/stl_iterator_base_funcs.h:213:5: note: candidates are: 'template<class _InputIterator> _InputIterator std::next(_InputIterator, typename std::iterator_traits<_Iter>::difference_type)'
  213 |     next(_InputIterator __x, typename
      |     ^~~~
race.cpp:14:34: note:                 'int next'
   14 | int ans=-1,n,k,vis[mxn],sub[mxn],next,mx;
      |                                  ^~~~
race.cpp: In function 'void solve(int)':
race.cpp:89:5: error: reference to 'next' is ambiguous
   89 |  id=next;
      |     ^~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:66,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from race.cpp:4:
/usr/include/c++/10/bits/stl_iterator_base_funcs.h:213:5: note: candidates are: 'template<class _InputIterator> _InputIterator std::next(_InputIterator, typename std::iterator_traits<_Iter>::difference_type)'
  213 |     next(_InputIterator __x, typename
      |     ^~~~
race.cpp:14:34: note:                 'int next'
   14 | int ans=-1,n,k,vis[mxn],sub[mxn],next,mx;
      |                                  ^~~~