Submission #697748

#	Time	Username	Problem	Language	Result	Execution time	Memory
697748		vjudge1	Torrent (COI16_torrent)	C++17	100 / 100	196 ms	16236 KiB

torrent

#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;T f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-')f=-1;
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
template <typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
template <typename T> void print(T x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9) print(x/10);
	putchar(x%10+48);
}
template <typename T> void print(T x,char c){print(x); putchar(c);}
template<typename T>inline void output(T x){print(x,' ');}
template<typename T,typename ...Arg>inline void output(T x,Arg ...arg){output(x);output(arg...);}
const int N=300007,inf=0x3f3f3f3f;
int n,rt[2],cnt,h[N],dp[N],pa[N],poss; vector<int>tmp,pos;
struct edge{int to,nxt;}mp[N<<1];
void add(int x,int y)
{
	cnt++;
	mp[cnt].nxt=h[x];
	mp[cnt].to=y;
	h[x]=cnt;
}
void prework(int x,int fa)
{
	pa[x]=fa;
	for(int i=h[x];i;i=mp[i].nxt)
	{
		int y=mp[i].to;
		if(y==fa) continue;
		prework(y,x);
	}
	tmp.clear();
	for(int i=h[x];i;i=mp[i].nxt)
		if(mp[i].to!=fa)
			tmp.push_back(dp[mp[i].to]);
	sort(tmp.begin(),tmp.end());
	reverse(tmp.begin(),tmp.end());
	for(int i=1;i<=tmp.size();i++)
		dp[x]=max(dp[x],tmp[i-1]+i);
}
void init()
{
	int now=rt[1];
	while(now!=rt[0])
		pos.push_back(now),now=pa[now];
}
int sol(int x)
{
	if(x==poss) return -inf;
	vector<int>vvv; int xxx=0;
	for(int i=h[x];i;i=mp[i].nxt)
		if(mp[i].to!=pa[x])
			vvv.push_back(sol(mp[i].to));
	sort(vvv.begin(),vvv.end());
	reverse(vvv.begin(),vvv.end());
	for(int i=1;i<=vvv.size();i++)
		xxx=max(xxx,vvv[i-1]+i);
	return xxx;
}
bool check(int x)
{
	poss=-1; int tim=x;
	for(int i=0;i<pos.size();i++)
	{
		tmp.clear(); int ok=1;
		for(int j=h[pos[i]];j;j=mp[j].nxt)
			if(mp[j].to!=pa[pos[i]]&&(i==0||mp[j].to!=pos[i-1]))
				tmp.push_back(dp[mp[j].to]);
		sort(tmp.begin(),tmp.end());
		reverse(tmp.begin(),tmp.end());
		for(int j=0;j<tmp.size();j++)
		{
			tmp[j]+=j+1;
			if(tmp[j]>tim) ok=0;
		}
		if(!ok) break;
		ok=tmp.size();
		for(int j=tmp.size()-1;j>=0;j--)
		{
			if(tmp[j]==tim) break;
			ok=j;
		}
		tim--; tim-=ok; poss=pos[i];
	}
	if(poss==-1) return false;
	return sol(rt[0])<=x;
}
int main()
{
	read(n,rt[0],rt[1]);
	for(int i=1,x,y;i<n;i++)
		read(x,y),add(x,y),add(y,x);
	prework(rt[0],0); init();
	int ml=0,mr=n,ans;
	while(ml<=mr)
	{
		int mid=(ml+mr)>>1;
		if(check(mid)) ans=mid,mr=mid-1;
		else ml=mid+1;
	}
	print(ans,'\n');
	return 0;
} 

Compilation message (stderr)

torrent.cpp: In function 'void prework(int, int)':
torrent.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i=1;i<=tmp.size();i++)
      |              ~^~~~~~~~~~~~
torrent.cpp: In function 'int sol(int)':
torrent.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(int i=1;i<=vvv.size();i++)
      |              ~^~~~~~~~~~~~
torrent.cpp: In function 'bool check(int)':
torrent.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i=0;i<pos.size();i++)
      |              ~^~~~~~~~~~~
torrent.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int j=0;j<tmp.size();j++)
      |               ~^~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:17:51: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 | template <typename T> void print(T x,char c){print(x); putchar(c);}
      |                                              ~~~~~^~~
torrent.cpp:101:16: note: 'ans' was declared here
  101 |  int ml=0,mr=n,ans;
      |                ^~~

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