Submission #697271

#	Time	Username	Problem	Language	Result	Execution time	Memory
697271		vjudge1	Torrent (COI16_torrent)	C++17	100 / 100	147 ms	48336 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,rt,ort,ct,fa[N],f[N],link[N];
vector<int>ed[N],ddp[N],dp[N];
void dfs(int x){
	for(int y:ed[x])if(y!=fa[x])fa[y]=x,dfs(y),ddp[x].push_back(f[y]);
	sort(ddp[x].begin(),ddp[x].end(),greater<int>());
	int sum=0;
	for(int y:ddp[x])f[x]=max(f[x],y+(++sum));
}
bool check(int x){
	int l,r,nx=x;
	for(l=1;l<=ct;l++){
        int mx=1,pd=0;
		for(int o=0;o<(int)dp[link[l]].size();o++){
			if(dp[link[l]][o]>x){pd=1;break;}
			else if(dp[link[l]][o]==x) mx=o+2;
        }
		if(pd){l--;break;}
		x-=mx;
	}
	for(r=ct;r;r--){
		int mx=1,pd=0;
		for(int o=0;o<(int)dp[link[r]].size();o++){
			if(dp[link[r]][o]>nx) {pd=1;break;}
			else if(dp[link[r]][o]==nx) mx=o+2;
        }
		if(pd){r++;break;}
		nx-=mx;
	}
	return l+1>=r;
}
int main(){
	scanf("%d%d%d",&n,&rt,&ort);
	for(int i=1,u,ddp;i<n;i++) scanf("%d%d",&u,&ddp),ed[u].push_back(ddp),ed[ddp].push_back(u);
	dfs(rt);
    link[ct=1]=ort;
	for(int x=ort;x!=rt;x=fa[x])link[++ct]=fa[x];
	for(int i=1;i<=ct;i++){
		dp[link[i]]=ddp[link[i]];
		if(i!=1)for(int o=0;o<(int)dp[link[i]].size();o++)if(dp[link[i]][o]==f[link[i-1]]){dp[link[i]].erase(dp[link[i]].begin()+o);break;}
		int sum=0;
		for(int& x:dp[link[i]])x+=(++sum);
	}
	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\n",ans);
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%d%d",&n,&rt,&ort);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:36:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  for(int i=1,u,ddp;i<n;i++) scanf("%d%d",&u,&ddp),ed[u].push_back(ddp),ed[ddp].push_back(u);
      |                             ~~~~~^~~~~~~~~~~~~~~~

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