oj.uz

Submission #310963

# Submission time Handle Problem Language Result Execution time Memory
310963 2020-10-08T20:48:37 Z CaroLinda Torrent (COI16_torrent) C++14
100 / 100
 524 ms 27056 KB 
#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

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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 5 ms 7296 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 20232 KB Output is correct
2 Correct 524 ms 25304 KB Output is correct
3 Correct 499 ms 26644 KB Output is correct
4 Correct 523 ms 25892 KB Output is correct
5 Correct 473 ms 23800 KB Output is correct
6 Correct 470 ms 24464 KB Output is correct
7 Correct 441 ms 27056 KB Output is correct