Submission #310963

#	Time	Username	Problem	Language	Result	Execution time	Memory
310963		CaroLinda	Torrent (COI16_torrent)	C++14	100 / 100	524 ms	27056 KiB

torrent

#include <bits/stdc++.h>
 
#define all(x) x.begin(),x.end()
#define debug 
#define pii pair<int,int>
#define ff first
#define ss second
#define sz(x) (int)(x.size())
 
const int MAXN = 3e5+10 ;
 
using namespace std ;
 
int n , a , b ;
int dp[MAXN] ;
bool vis[MAXN] ;
vector<int> inMiddle ;
vector<int> adj[MAXN] ;
 
bool dfs1(int x, int father )
{
	bool ok = (x == b) ? true : false ;
 
	for(auto e : adj[x])
	{
		if(e == father) continue ;
		ok |= dfs1(e,x) ;
 
	}
 
	if(ok) inMiddle.push_back(x) ;
 
	return ok ;
}
 
void dfs2(int x)
{
	vis[x] = true ;
	vector<int> dpChildren ;
 
	for(auto e : adj[x])
	{
		if(vis[e]) continue ;
		dfs2(e) ;
		dpChildren.push_back(dp[e]) ;
	}
	sort(all(dpChildren)) ;
	reverse(all(dpChildren)) ;
 
	dp[x] = 0 ;
	for(int i = 0 ; i < sz(dpChildren);i++ )
		dp[x] = max(dp[x], i+1 + dpChildren[i]) ;
 
}
 
int main()
{
	scanf("%d%d%d", &n, &a, &b ) ;
	for(int i = 0 , x , y ; i <n-1 ; i++ )
	{
		scanf("%d%d", &x, &y ) ;
 
		adj[x].push_back(y) ;
		adj[y].push_back(x); 
 
	}
 
	dfs1(a,-1) ;
	reverse(all(inMiddle)) ;
 
	for(auto v : inMiddle ) debug("%d " , v );
	debug("\n") ;
 
	int l = 1 , r = sz(inMiddle)-1 , mid , ans = n ;
 
	//the last one in inMiddle is b
 
	while(l <= r)
	{
		mid = (l+r)>>1 ;
 
		int idx = inMiddle[mid] ;

		for(int i = 1 ; i <= n ; i++ ) vis[i] = false ;

		vis[idx] = true ;
		dfs2(a) ;

		vis[idx] = false ;
		dfs2(b) ;

		ans = min(ans, max(dp[a], dp[b])) ;

		if(dp[a] > dp[b]) r = mid-1 ;
		else l = mid+1 ;
 
	} 
 
	printf("%d\n" , ans ) ;
 
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:71:32: warning: left operand of comma operator has no effect [-Wunused-value]
   71 |  for(auto v : inMiddle ) debug("%d " , v );
      |                                ^~~~~
torrent.cpp:72:8: warning: statement has no effect [-Wunused-value]
   72 |  debug("\n") ;
      |       ~^~~~~
torrent.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |  scanf("%d%d%d", &n, &a, &b ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf("%d%d", &x, &y ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~

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