oj.uz

Submission #519937

# Submission time Handle Problem Language Result Execution time Memory
519937 2022-01-27T20:08:31 Z CaroLinda Meetings 2 (JOI21_meetings2) C++14
0 / 100
 20 ms 41036 KB 
#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] ;
}

void print(int pos, int l, int r){
	cout << l <<" " << r <<": " ;
	auto e = tree[pos] ;
	cout << e.a <<" " << e.b <<" " << e.ab <<" " << e.ba <<" " << e.aba <<  endl ;
	if( l == r ) return ;
	int mid=(l+r)>>1 ;
	print(pos<<1 , l , mid) ;
	print(pos<<1|1, mid+1, r) ;
}

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] ) ;

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 40912 KB Output is correct
2 Correct 19 ms 41000 KB Output is correct
3 Correct 19 ms 41036 KB Output is correct
4 Correct 20 ms 41028 KB Output is correct
5 Incorrect 19 ms 40976 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 40912 KB Output is correct
2 Correct 19 ms 41000 KB Output is correct
3 Correct 19 ms 41036 KB Output is correct
4 Correct 20 ms 41028 KB Output is correct
5 Incorrect 19 ms 40976 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 40912 KB Output is correct
2 Correct 19 ms 41000 KB Output is correct
3 Correct 19 ms 41036 KB Output is correct
4 Correct 20 ms 41028 KB Output is correct
5 Incorrect 19 ms 40976 KB Output isn't correct
6 Halted 0 ms 0 KB -