Submission #897807

#	Time	Username	Problem	Language	Result	Execution time	Memory
897807		lolismek	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	2212 ms	28344 KiB

meetings2

#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <iomanip>
#include <cassert>

#include <random>
#include <chrono>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ull = unsigned long long;
using ll = long long;

//#define int __int128
//#define int ll
#define pii pair <int, int>
#define all(a) (a).begin(), (a).end()
#define fr first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound

#define vt vector
#define FOR(a, b) for(int i = (a); i <= (b); i++)
#define FORr(a, b) for(int i = (a); i >= (b); i--)
#define sz(x) (int)(x).size()

#define YES cout << "YES\n"
#define NO cout << "NO\n"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rangerng(int l, int r){
    return uniform_int_distribution<>(l, r)(rng);
}

////////////////////////////////////////////////////////////////////////////////////

const int NMAX = 2e5;

int n;
vt <int> adj[NMAX + 1];

int sz[NMAX + 1];
bool proc[NMAX + 1];

void recalc_sz(int node, int par){
    sz[node] = 1;
    for(int child : adj[node]){
        if(child != par && !proc[child]){
            recalc_sz(child, node);
            sz[node] += sz[child];
        }
    }
}

int get_centroid(int node, int par, int lim){
    for(int child : adj[node]){
        if(child != par && !proc[child] && sz[child] > lim){
            return get_centroid(child, node, lim);
        }
    }
    return node;
}

namespace AINT{
    int aint[4 * NMAX + 1];

    void build(int node, int l, int r){
        aint[node] = 0;
        if(l == r){
            return;
        }

        int mid = (l + r) / 2;
        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);
    }

    void update(int node, int l, int r, int pos, int val){
        if(l == r){
            aint[node] = max(aint[node], val);
            return;
        }

        int mid = (l + r) / 2;
        if(pos <= mid){
            update(2 * node, l, mid, pos, val);
        }else{
            update(2 * node + 1, mid + 1, r, pos, val);
        }

        aint[node] = max(aint[2 * node], aint[2 * node + 1]);
    }

    void setUpdate(int node, int l, int r, int pos){
        if(l == r){
            aint[node] = 0;
            return;
        }

        int mid = (l + r) / 2;
        if(pos <= mid){
            setUpdate(2 * node, l, mid, pos);
        }else{
            setUpdate(2 * node + 1, mid + 1, r, pos);
        }
        aint[node] = max(aint[2 * node], aint[2 * node + 1]);
    }

    int query(int node, int l, int r, int ql, int qr){
        if(ql <= l && r <= qr){
            return aint[node];
        }

        int mid = (l + r) / 2, ans = 0;
        if(ql <= mid){
            ans = max(ans, query(2 * node, l, mid, ql, qr));
        }
        if(mid + 1 <= qr){
            ans = max(ans, query(2 * node + 1, mid + 1, r, ql, qr));
        }
        return ans;
    }
}

int ans[NMAX + 1];

int aux;

void dfs1(int node, int par, int lvl){    
    int mx = AINT::query(1, 1, n, sz[node], n);
    //cout << "-- " << node << ' ' << lvl << ' ' << mx << endl;
    if(mx > 0){
        ans[sz[node]] = max(ans[sz[node]], lvl + mx - 1);
    }
    //AINT::update(1, 1, n, sz[node], lvl);

    ans[min(sz[node], aux)] = max(ans[min(sz[node], aux)], lvl);

    for(int child : adj[node]){
        if(child != par && !proc[child]){
            dfs1(child, node, lvl + 1);
        }
    }
}

void dfs3(int node, int par, int lvl){
    AINT::update(1, 1, n, sz[node], lvl);

    for(int child : adj[node]){
        if(child != par && !proc[child]){
            dfs3(child, node, lvl + 1);
        }
    }
}

void dfs2(int node, int par, int lvl){    
    AINT::setUpdate(1, 1, n, sz[node]);

    for(int child : adj[node]){
        if(child != par && !proc[child]){
            dfs2(child, node, lvl + 1);
        }
    }
}

void decomp(int node){
    recalc_sz(node, 0);
    int centroid = get_centroid(node, 0, sz[node] / 2);
    recalc_sz(centroid, 0);

    proc[centroid] = 1;

    //cout << ">> " << centroid << endl;

    for(int child : adj[centroid]){
        if(!proc[child]){
            aux = sz[centroid] - sz[child];
            dfs1(child, centroid, 2);
            dfs3(child, centroid, 2);
        }
    }

    for(int child : adj[centroid]){
        if(!proc[child]){
            dfs2(child, centroid, 2);
        }
    }

    //cout << "---------\n";
    reverse(all(adj[centroid]));

    for(int child : adj[centroid]){
        if(!proc[child]){
            dfs1(child, centroid, 2);
            dfs3(child, centroid, 2);
        }
    }

    for(int child : adj[centroid]){
        if(!proc[child]){
            dfs2(child, centroid, 2);
        }
    }

    for(int vec : adj[centroid]){
        if(!proc[vec]){
            decomp(vec);
        }
    }
}   

void solve(){
    cin >> n;

    FOR(1, n - 1){
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    AINT::build(1, 1, n);
    decomp(1);

    for(int i = n - 1; i >= 1; i--){
        ans[i] = max(ans[i], ans[i + 1]);
    }

    for(int i = 1; i <= n; i++){
        if(i & 1){
            cout << 1 << '\n';
        }else{
            cout << max(1, ans[i / 2]) << '\n';
        }
    }
}


signed main(){

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

    int T;
    //cin >> T;

    T = 1;

    while(T--){
        solve();
    }

    return 0;
}

/*
16
13 3
16 13
16 5
16 8
3 12
11 16
14 8
15 12
3 10
10 2
16 1
6 10
11 9
8 4
1 7

1
7
1
5
1
5
1
3
1
3
1
3
1
2
1
1

*/

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