oj.uz

Submission #519938

# Submission time Handle Problem Language Result Execution time Memory
519938 2022-01-27T20:18:52 Z CaroLinda Meetings 2 (JOI21_meetings2) C++14
100 / 100
 435 ms 71728 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] ;
}

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

# Verdict Execution time Memory Grader output
1 Correct 20 ms 41036 KB Output is correct
2 Correct 21 ms 41044 KB Output is correct
3 Correct 19 ms 41036 KB Output is correct
4 Correct 19 ms 40948 KB Output is correct
5 Correct 19 ms 40928 KB Output is correct
6 Correct 19 ms 40956 KB Output is correct
7 Correct 23 ms 40960 KB Output is correct
8 Correct 20 ms 40908 KB Output is correct
9 Correct 20 ms 41032 KB Output is correct
10 Correct 21 ms 41008 KB Output is correct
11 Correct 24 ms 41008 KB Output is correct
12 Correct 24 ms 40964 KB Output is correct
13 Correct 18 ms 41036 KB Output is correct
14 Correct 18 ms 41036 KB Output is correct
15 Correct 18 ms 41032 KB Output is correct
16 Correct 19 ms 40960 KB Output is correct
17 Correct 19 ms 41032 KB Output is correct
18 Correct 19 ms 40976 KB Output is correct
19 Correct 20 ms 41040 KB Output is correct
20 Correct 20 ms 41132 KB Output is correct
21 Correct 20 ms 40936 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 41036 KB Output is correct
2 Correct 21 ms 41044 KB Output is correct
3 Correct 19 ms 41036 KB Output is correct
4 Correct 19 ms 40948 KB Output is correct
5 Correct 19 ms 40928 KB Output is correct
6 Correct 19 ms 40956 KB Output is correct
7 Correct 23 ms 40960 KB Output is correct
8 Correct 20 ms 40908 KB Output is correct
9 Correct 20 ms 41032 KB Output is correct
10 Correct 21 ms 41008 KB Output is correct
11 Correct 24 ms 41008 KB Output is correct
12 Correct 24 ms 40964 KB Output is correct
13 Correct 18 ms 41036 KB Output is correct
14 Correct 18 ms 41036 KB Output is correct
15 Correct 18 ms 41032 KB Output is correct
16 Correct 19 ms 40960 KB Output is correct
17 Correct 19 ms 41032 KB Output is correct
18 Correct 19 ms 40976 KB Output is correct
19 Correct 20 ms 41040 KB Output is correct
20 Correct 20 ms 41132 KB Output is correct
21 Correct 20 ms 40936 KB Output is correct
22 Correct 27 ms 41344 KB Output is correct
23 Correct 22 ms 41312 KB Output is correct
24 Correct 26 ms 41436 KB Output is correct
25 Correct 22 ms 41420 KB Output is correct
26 Correct 24 ms 41428 KB Output is correct
27 Correct 24 ms 41436 KB Output is correct
28 Correct 25 ms 41420 KB Output is correct
29 Correct 23 ms 41380 KB Output is correct
30 Correct 24 ms 41428 KB Output is correct
31 Correct 22 ms 41540 KB Output is correct
32 Correct 22 ms 41548 KB Output is correct
33 Correct 22 ms 41636 KB Output is correct
34 Correct 23 ms 41420 KB Output is correct
35 Correct 23 ms 41420 KB Output is correct
36 Correct 24 ms 41428 KB Output is correct
37 Correct 22 ms 41348 KB Output is correct
38 Correct 25 ms 41464 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 41036 KB Output is correct
2 Correct 21 ms 41044 KB Output is correct
3 Correct 19 ms 41036 KB Output is correct
4 Correct 19 ms 40948 KB Output is correct
5 Correct 19 ms 40928 KB Output is correct
6 Correct 19 ms 40956 KB Output is correct
7 Correct 23 ms 40960 KB Output is correct
8 Correct 20 ms 40908 KB Output is correct
9 Correct 20 ms 41032 KB Output is correct
10 Correct 21 ms 41008 KB Output is correct
11 Correct 24 ms 41008 KB Output is correct
12 Correct 24 ms 40964 KB Output is correct
13 Correct 18 ms 41036 KB Output is correct
14 Correct 18 ms 41036 KB Output is correct
15 Correct 18 ms 41032 KB Output is correct
16 Correct 19 ms 40960 KB Output is correct
17 Correct 19 ms 41032 KB Output is correct
18 Correct 19 ms 40976 KB Output is correct
19 Correct 20 ms 41040 KB Output is correct
20 Correct 20 ms 41132 KB Output is correct
21 Correct 20 ms 40936 KB Output is correct
22 Correct 27 ms 41344 KB Output is correct
23 Correct 22 ms 41312 KB Output is correct
24 Correct 26 ms 41436 KB Output is correct
25 Correct 22 ms 41420 KB Output is correct
26 Correct 24 ms 41428 KB Output is correct
27 Correct 24 ms 41436 KB Output is correct
28 Correct 25 ms 41420 KB Output is correct
29 Correct 23 ms 41380 KB Output is correct
30 Correct 24 ms 41428 KB Output is correct
31 Correct 22 ms 41540 KB Output is correct
32 Correct 22 ms 41548 KB Output is correct
33 Correct 22 ms 41636 KB Output is correct
34 Correct 23 ms 41420 KB Output is correct
35 Correct 23 ms 41420 KB Output is correct
36 Correct 24 ms 41428 KB Output is correct
37 Correct 22 ms 41348 KB Output is correct
38 Correct 25 ms 41464 KB Output is correct
39 Correct 386 ms 60440 KB Output is correct
40 Correct 375 ms 60060 KB Output is correct
41 Correct 435 ms 60464 KB Output is correct
42 Correct 395 ms 60840 KB Output is correct
43 Correct 412 ms 60836 KB Output is correct
44 Correct 388 ms 60784 KB Output is correct
45 Correct 356 ms 66488 KB Output is correct
46 Correct 332 ms 71728 KB Output is correct
47 Correct 347 ms 61448 KB Output is correct
48 Correct 304 ms 61856 KB Output is correct
49 Correct 330 ms 61792 KB Output is correct
50 Correct 301 ms 61996 KB Output is correct
51 Correct 298 ms 69004 KB Output is correct