Submission #310962

#	Time	Username	Problem	Language	Result	Execution time	Memory
310962		CaroLinda	Torrent (COI16_torrent)	C++14	31 / 100	2084 ms	25596 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 = 0 , r = n , mid , ans = n ;

	//the last one in inMiddle is b

	while(l <= r)
	{
		mid = (l+r)>>1 ;

		int low = 1 , high = sz(inMiddle)-1 , m ;
		int lastIndex = 1 ;

		while( low <= high )
		{
			m = (low+high)>>1 ;

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

			dfs2(a) ;

			if(dp[a] <= mid)
			{
				lastIndex = m ;
				low = m+1 ;
			}
			else high = m-1 ;

		}

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

		vis[ inMiddle[lastIndex] ] = true ;
		dfs2(a) ;

		vis[ inMiddle[lastIndex] ]= false ;
		dfs2(b) ;

		if( max(dp[a],dp[b]) <= mid )
		{
			ans = mid ;
			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: 0 / 69