Submission #310745

#	Time	Username	Problem	Language	Result	Execution time	Memory
310745		CaroLinda	Torrent (COI16_torrent)	C++14	69 / 100	228 ms	49756 KiB

torrent

#include <bits/stdc++.h>

#define sz(x) (int)(x.size())

const int MAXN = 3e5+10 ;

using namespace std ;

int n , a[2] ;
int cor[MAXN] ;
int dist[MAXN][2] ;
vector<int> adj[MAXN] , adj2[MAXN] ;
vector<pair<int,int> > edge ;

void dfs(int x, int father, int idx )
{
	for(auto e : adj2[x])
	{
		if(e == father ) continue ;

		dist[e][idx] = dist[x][idx]+1 ;
		dfs(e,x,idx ) ;

	}
}

int dfs2(int x, int father )
{

	vector<int> children ;
	for(auto e : adj[x])
	{
		if(e == father) continue ;
		children.push_back(dfs2(e,x)) ;
	}
	sort(children.begin() , children.end()) ;
	reverse(children.begin() , children.end()) ;

	int ans = 0 ;
	for(int i = 0 ; i < sz(children) ; i++ )
		ans = max(ans, children[i]+i+1 ) ;

	return ans ;

}

int main()
{
	scanf("%d%d%d", &n , &a[0] , &a[1] ) ;
	for(int i = 0 , u , v ; i <n-1 ; i++ )
	{
		scanf("%d%d", &u, &v ) ;
		edge.push_back(make_pair(u,v)) ;
		adj2[u].push_back(v) ;
		adj2[v].push_back(u);

	}

	dfs(a[0] , -1 , 0) ;
	dfs(a[1] ,-1 , 1 ) ;

	for(int i = 1 ; i <= n ; i++)
	{
		if( dist[i][0] < dist[i][1] )
			cor[i] = 0 ;
		else cor[i] = 1 ;
	}

	for(auto e : edge )
	{
		int u = e.first ;
		int v = e.second ;
		if(cor[u] != cor[v]) continue ;
		adj[u].push_back(v) ;
		adj[v].push_back(u) ;
	}

	int ans = dfs2(a[0] , -1 ) ;
	ans = max(ans,dfs2(a[1],-1) ) ;

	printf("%d\n" , ans ) ;

}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d%d%d", &n , &a[0] , &a[1] ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |   scanf("%d%d", &u, &v ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~

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