Submission #997566

#	Time	Username	Problem	Language	Result	Execution time	Memory
997566		hotboy2703	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	450 ms	44476 KiB

meetings2

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2e5+100;
ll n;
vector <ll> g[MAXN];
bool del[MAXN];
ll sz[MAXN];
ll sub[MAXN];
ll in[MAXN];
ll out[MAXN];
ll max1[MAXN];
ll ans[MAXN];
ll timeDFS;
void dfs_sub(ll u,ll p){
    in[u] = ++timeDFS;
    sub[u] = 1;
    for (auto v:g[u]){
        if (v==p)continue;
        dfs_sub(v,u);
        sub[u] += sub[v];
    }
    out[u] = timeDFS;
}
void dfs_sz(ll u,ll p){
    sz[u] = 1;
    for (auto v:g[u]){
        if (del[v] || v==p)continue;
        dfs_sz(v,u);
        sz[u]+=sz[v];
    }
}
ll f(ll x,ll y){
    if (in[x] <= in[y] && in[y] <= out[x])return n-sub[y];
    else return sub[x];
}
ll find_centroid(ll u,ll p,ll root){
    for (auto v:g[u]){
        if (del[v] || v==p)continue;
        if (sz[v]*2>sz[root]){
            return find_centroid(v,u,root);
        }
    }
    return u;
}
struct node{
    ll comp,u,sz,dist;
};
vector <node> all;
void dfs(ll u,ll p,ll root1,ll root2,ll dist){
    all.push_back({root1,u,f(u,p),dist});
    for (auto v:g[u]){
        if (del[v] || v==p)continue;
        dfs(v,u,root1,root2,dist+1);
    }
}
void solve_centroid(ll u){
    dfs_sz(u,u);
    u = find_centroid(u,u,u);
    all.clear();
    for (auto v:g[u]){
        if (!del[v]){
            max1[v] = -1;
            dfs(v,u,v,u,1);
        }
    }
    sort(all.begin(),all.end(),[](node x,node y){return x.sz > y.sz;});
    ll best1 = 0,best2 = 0;
//    cout<<"CENTROID "<<u<<endl;
    for (auto x:all){
//        cout<<x.comp<<' '<<x.u<<' '<<x.sz<<' '<<x.dist<<'\n';
        if (best1 != 0 && best1 != x.comp)ans[x.sz] = max(ans[x.sz],x.dist+max1[best1]);
        else if (best2 != 0)ans[x.sz] = max(ans[x.sz],x.dist+max1[best2]);

        max1[x.comp] = max(max1[x.comp],x.dist);

        vector <ll> tmp = {best1,best2,x.comp};
        sort(tmp.begin(),tmp.end(),[](ll x,ll y){return max1[x] > max1[y];});
        tmp.resize(unique(tmp.begin(),tmp.end())-tmp.begin());
        best1 = tmp[0],best2 = tmp[1];
        ll sus = min(x.sz,f(u,x.comp));
        ans[sus] = max(ans[sus], x.dist);
    }
    del[u] = 1;
    for (auto v:g[u]){
        if (!del[v])solve_centroid(v);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n;
    for (ll i = 1;i < n;i ++){
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (ll i = 1;i <= n;i ++)sort(g[i].begin(),g[i].end());
    dfs_sub(1,1);
    solve_centroid(1);
    for (ll i = n;i >= 1;i --){
        ans[i] = max(ans[i],ans[i+1]);
    }
    for (ll i = 1;i <= n;i ++){
        if (i%2)cout<<1<<'\n';
        else cout<<ans[i/2]+1<<'\n';
    }
    return 0;
}

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