Submission #519938

#	Time	Username	Problem	Language	Result	Execution time	Memory
519938		CaroLinda	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	435 ms	71728 KiB

meetings2

#include <bits/stdc++.h>
 
#define mkt make_tuple
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define ll long long
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define pii pair<int,int>
#define mk make_pair
#define ff first
#define ss second
#define tiii tuple<int,int,int>
#define pb push_back

const int MAX = 2e5+10 ;

using namespace std ;

struct Node
{

    int a , b , ab , ba , aba ;

    Node() { a = b = ab = ba = aba = -MAX ; }

    Node operator + ( Node other ) const
    {
        Node ret ;

        ret.ab = max({ ab, other.ab , a + other.b }) ;
        ret.ba = max( {ba, other.ba , b + other.a} ) ;
        ret.aba = max( {aba,other.aba , ab + other.a , a + other.ba} ) ;
        ret.a = max( a , other.a ) ;
        ret.b = max( b, other.b ) ;

        return ret;

    }

} tree[MAX*8] ;

int N ;
int sub[MAX ] , ans[MAX] , dist[MAX] , h[MAX] ;
vector<int> adj[MAX] ;
vector<pii> edg ;
 
void dfs1(int x, int par){
	sub[x] = 1 ;
	for(auto e : adj[x] ){
		if(e == par ) continue ;
		dfs1(e,x) ;
		sub[x] += sub[e] ;
	}
}

int tin[MAX];
int currTime ;
vector<int> v[MAX] ;
void dfs2(int x, int par){
	v[x].pb(++currTime ) ;
	sub[x] = 1 ;
	for(auto e : adj[x] ){
		if(e == par ) continue ;
		h[e]=h[x]+1 ;
		dfs2(e,x) ;
		v[x].pb(++currTime) ;
		sub[x] += sub[e] ;
		edg.pb(mk(min(sub[e], N-sub[e]) , e ) ) ;
	}
}

void upd(int pos, int l, int r,int x,  int val ){
	if(l == r ){
		tree[pos].a = val ;
		tree[pos].b = -2*val ;
		tree[pos].ab = -val ;
		tree[pos].ba = -val ;
		return ;
	}
	int mid = (l+r)>>1 ;
	if(x <= mid ) upd(pos<<1 , l , mid , x , val ) ;
	else upd(pos<<1|1, mid+1, r, x, val ) ;
	tree[pos] = tree[pos<<1]+tree[pos<<1|1] ;
}

int main(){

	ios_base::sync_with_stdio(false) ;
	cin.tie(0) ;

	cin >> N ;
	for(int i = 0 , a , b ; i < N-1 ; i++ ){
		cin >> a >> b ;
		adj[a].pb(b) ;
		adj[b].pb(a) ;
	}

	dfs1(1,-1) ;
	int cn = 1 ;
	for(int i = 2 ; i <= N ; i++ )
		if( sub[i] < sub[cn] && sub[i] > N/2 )  cn = i ;

	dfs2(cn,-1) ;

	auto coloca = [&](int x){
		for(auto e : v[x] ) upd(1,1,currTime, e, h[x] ) ;
	} ;

	coloca(cn) ;

	sort(all(edg) ) ; reverse(all(edg) ) ;

	for(auto e : edg ){
		int a = e.ff , b = e.ss ;
		coloca(b) ;
		ans[a] = max(ans[a], tree[1].aba+1) ;
	}
	for(int i = N ; i >= 0 ; i-- ) ans[i] = max({ans[i], ans[i+1] ,1}) ;

	for(int i = 1 ; i <= N ; i++ ) {
		if( (i%2) == 1 ) cout << "1\n" ;
		else cout << ans[i>>1] <<"\n" ;
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80