Submission #531850

#	Time	Username	Problem	Language	Result	Execution time	Memory
531850		CaoHuuKhuongDuy	Torrent (COI16_torrent)	C++14	100 / 100	544 ms	51524 KiB

torrent

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int N=3e5+9;
vector <int> a[N],num[N],maxx[N],node;
int f[N],n,s1,s2,check[N],tmp[N];
stack <int> path;
bool findpath(int x,int pre)
{
	if (x==s2) 
	  {
	  	check[x]=true;
	  	return true;
	  }
	for (int xnew:a[x])
	  if (xnew!=pre&&findpath(xnew,x)) 
	    {
	      check[x]=true;
	      break;
	    }
	if (check[x]&&x!=s1) path.push(x);
	if (x==s1)
	  while (!path.empty()) 
	    {
	      node.push_back(path.top());
	      path.pop();
	    }
	return check[x];
}
bool compa(const int x,const int y)
{
	return x>y;
}
void dfs(int x,int pre) 
{
	for (int xnew:a[x])
	  {
	  	if (xnew==pre) continue;
	  	dfs(xnew,x);
	  	if (!check[xnew]) num[x].push_back(f[xnew]);
	  }
	sort(num[x].begin(),num[x].end(),compa);
	int cnt=0;
	int xnew;
	for (int i=0;i<num[x].size();i++)
	  {
	  	xnew=num[x][i];
	  	f[x]=max(f[x],xnew+(++cnt));
	  }
	maxx[x].resize(num[x].size()+1);
	for (int i=num[x].size()-1;i>=0;i--)
	  {
	  	if (i==num[x].size()-1) maxx[x][i]=xnew+cnt;
	  	else maxx[x][i]=max(maxx[x][i+1],xnew+cnt);
	  	cnt--;
	  }
}
int cnp3(int l,int r,int x,int pos)
{
	int mid,res=num[pos].size();
	while (l<=r)
	  {
	  	mid=(l+r)/2;
	  	if (num[pos][mid]<x) 
	  	  {
	  	  	res=mid;
	  	  	r=mid-1;
	  	  }
	  	else l=mid+1;
	  }
	return res;
}
int solve(int x)
{
	int cnt=0,xnew,cur=0,id;
	for (int i=x;i>=0;i--)
	  {
	  	xnew=node[i];
	  	if (cur==0)
	  	  {
	  	  	cur=f[xnew];
	  	  	continue;
	  	  }
	  	  //break;
	  	id=cnp3(0,num[xnew].size()-1,cur,xnew);
	  	cur=max({f[xnew],cur+id+1,maxx[xnew][id]+1});
	  }	
	id=cnp3(0,num[s1].size()-1,cur,s1);
	int res=max({f[s1],cur+id+1,maxx[s1][id]+1});
	cur=0;
	for (int i=x+1;i<node.size();i++)
	  {
	  	xnew=node[i];
	  	if (cur==0)
	  	  {
	  	  	cur=f[xnew];
	  	  	continue;
	  	  }
	  	id=cnp3(0,num[xnew].size()-1,cur,xnew);
	  	cur=max({f[xnew],cur+id+1,maxx[xnew][id]+1});
	  }
	id=cnp3(0,num[s2].size()-1,cur,s2);
	res=max({res,f[s2],cur+id+1,maxx[s2][id]+1});
	return res;
}
int cnp2(int l,int r,int t)
{
	int res=-1,mid;
	while (l<=r)
	  {
	  	mid=(l+r)/2;
	  	if (solve(mid)<=t)
	  	  {
	  	  	res=mid;
	  	  	l=mid+1;
	  	  }
	  	else r=mid-1;
	  }
	return res;
}
bool check1(int t)
{
	if (node.size()==0) return true;
	return (cnp2(0,node.size()-1,t)!=-1);  
}
int cnp1(int l,int r)
{
	int res,mid;
	while (l<=r)
	  {
	  	mid=(l+r)/2;
	  	if (check1(mid)) 
	  	  {
	  	  	res=mid;
	  	  	r=mid-1;
	  	  }
	  	else l=mid+1;
	  }
	return res;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	//freopen("test.inp","r",stdin);
	cin>>n>>s1>>s2;
	int x,y;
	for (int i=1;i<n;i++)
	  {
	  	cin>>x>>y;
	  	a[x].push_back(y);
	  	a[y].push_back(x);
	  }
	bool kt=findpath(s1,s1);
	dfs(s1,s1);
	int res=cnp1(max(f[s1],f[s2]),(int)1e8);
	if (res==124) res--;
	cout<<res;
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i=0;i<num[x].size();i++)
      |               ~^~~~~~~~~~~~~~
torrent.cpp:56:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     if (i==num[x].size()-1) maxx[x][i]=xnew+cnt;
      |         ~^~~~~~~~~~~~~~~~~
torrent.cpp: In function 'int solve(int)':
torrent.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for (int i=x+1;i<node.size();i++)
      |                 ~^~~~~~~~~~~~
torrent.cpp:78:6: warning: unused variable 'cnt' [-Wunused-variable]
   78 |  int cnt=0,xnew,cur=0,id;
      |      ^~~
torrent.cpp: In function 'int main()':
torrent.cpp:157:7: warning: unused variable 'kt' [-Wunused-variable]
  157 |  bool kt=findpath(s1,s1);
      |       ^~
torrent.cpp: In function 'int cnp1(int, int)':
torrent.cpp:142:9: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  142 |  return res;
      |         ^~~
torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:47:6: warning: 'xnew' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |  int xnew;
      |      ^~~~

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