Submission #697584

#	Time	Username	Problem	Language	Result	Execution time	Memory
697584		vjudge1	Torrent (COI16_torrent)	C++14	100 / 100	116 ms	19756 KiB

torrent

#include<bits/stdc++.h> 
using namespace std;
const int N=3e5+5;
int n,a,b,u,v,h[N],tot,fa[N],c[N],k,f[N],F[N],G[N],l,r,mid,ans;
struct edge {int to,nxt;}e[N<<1];
void add(int u,int v) 
{
	e[++tot]={v,h[u]};
	h[u]=tot;
}
void dfs(int u)
{
	vector<int> p;int id=0;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa[u]) continue;
		fa[v]=u;dfs(v);p.push_back(f[v]);
	}
	sort(begin(p),end(p));reverse(begin(p),end(p));
	for(int x:p) id++,f[u]=max(f[u],id+x);
}
bool check(int mid)
{
	int step=mid,l=k,r=k+1;
	for(int i=1;i<=k;i++)
	{
		if(step<F[i]) {l=i-1;break;}
		if(step==F[i]) step-=G[i];
		else step--; 
	}
	step=mid;
	for(int i=k;i>=1;i--)
	{
		if(step<F[i]) {r=i+1;break;}
		if(step==F[i]) step-=G[i];
		else step--; 
	}
	return l+1>=r;
}
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs(a);
	while(b!=fa[a]) c[++k]=b,b=fa[b];
	reverse(c+1,c+k+1);
	for(int l=1;l<=k;l++)
	{
		u=c[l];
		int id=0;
		vector<int> p;set<int> s;
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			if(v==fa[u]||v==c[l+1]) continue;
			p.push_back(f[v]);
		}
		sort(begin(p),end(p));reverse(begin(p),end(p));
		for(int x:p) 
		{
			id++,F[l]=max(F[l],id+x);
			s.insert(id);
		}
		s.insert(id+1);
		for(int x:p) s.erase(--s.upper_bound(F[l]-x));
		G[l]=*begin(s);
	}
	l=0,r=n;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d%d%d",&n,&a,&b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
torrent.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69