Submission #697731

#	Time	Username	Problem	Language	Result	Execution time	Memory
697731		vjudge1	Torrent (COI16_torrent)	C++14	100 / 100	92 ms	48672 KiB

torrent

#include<bits/stdc++.h>
#define ll long long
#define lll __int128
#define db double
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
using namespace std;
namespace IO
{
	const int SZ=1<<20;
	char gchar()
	{
	    static char buf[SZ];
	    static int i=SZ;
	    if(i==SZ)i=0,fread(buf,1,SZ,stdin);
	    return buf[i++];
	}
	void pchar(char c)
	{
	    static char buf[SZ];
	    static int i=0;
	    if(c)buf[i++]=c;
	    if(!c||i==SZ)fwrite(buf,1,i,stdout),i=0;
	}
	void pstr(string s,char end='\n')
	{
		for(char c:s)pchar(c);
		pchar(end);
	}
	template<typename T>void read(T &u)
	{
	    u=0;int f=1;
	    static char c;
	    while((c=gchar())>'9'||c<'0')if(c=='-')f=-1;
	    u=c-'0';
	    while((c=gchar())>='0'&&c<='9')
			u=(u<<1)+(u<<3)+(c^48);
		u*=f;
	}
	template<typename T,typename ...Args>void read(T &u,Args&...args){read(u),read(args...);}
	template<typename T>void i_write(T u)
	{
	    if(u>9)i_write(u/10);
	    pchar(u%10+'0');
	}
	template<typename T>void write(T u,char end='\n')
	{
	    if(u<0)pchar('-'),u=-u;
	    if(u>9)i_write(u/10);
	    pchar(u%10+'0');
	    pchar(end);
	}
}
using IO::read;
using IO::write;
const int N=3e5+10;
int n,rt,ort,cnt,fa[N],f[N],link[N];
vector<int>e[N],g[N],dp[N];
void dfs(int u)
{
	for(int v:e[u])
		if(v!=fa[u])fa[v]=u,dfs(v),g[u].push_back(f[v]);
	sort(g[u].begin(),g[u].end(),greater<int>());
	int s=0;
	for(int v:g[u])s++,f[u]=max(f[u],v+s);
}
bool check(int x)
{
	int l,r,tmp=x;
	for(l=1;l<=cnt;l++)
	{
        int mx=1,flg=0;
		for(int j=0;j<(int)dp[link[l]].size();j++)
			if(dp[link[l]][j]>x){flg=1;break;}
			else if(dp[link[l]][j]==x)mx=j+2;
		if(flg){l--;break;}
		x-=mx;
	}
	for(r=cnt;r;r--)
	{
		int mx=1,flg=0;
		for(int j=0;j<(int)dp[link[r]].size();j++)
			if(dp[link[r]][j]>tmp){flg=1;break;}
			else if(dp[link[r]][j]==tmp)mx=j+2;
		if(flg){r++;break;}
		tmp-=mx;
	}
	return l+1>=r;
}
int main()
{
	read(n,rt,ort);
	for(int i=1,u,v;i<n;i++)
		read(u,v),e[u].push_back(v),e[v].push_back(u);
	dfs(rt),link[cnt=1]=ort;
	for(int u=ort;u!=rt;u=fa[u])link[++cnt]=fa[u];
	for(int i=1;i<=cnt;i++)
	{
		dp[link[i]]=g[link[i]];
		if(i!=1)
		{
			for(int j=0;j<(int)dp[link[i]].size();j++)
				if(dp[link[i]][j]==f[link[i-1]]){dp[link[i]].erase(dp[link[i]].begin()+j);break;}
		}
		int s=0;
		for(int &x:dp[link[i]])s++,x+=s;
	}
	int l=0,r=n,mid,ans=n;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d",ans);
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'char IO::gchar()':
torrent.cpp:18:24: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |      if(i==SZ)i=0,fread(buf,1,SZ,stdin);
      |                   ~~~~~^~~~~~~~~~~~~~~~

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