Submission #1238731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238731		damoon	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	369 ms	24496 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3,unroll-loops") //main
//#pragma GCC target("avx2") //cf...
//#pragma GCC target("sse4") //Quera

#define ll long long
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
#define f first
#define s second

#define lc 2*id
#define rc 2*id+1
#define all(x) x.begin(),x.end()

#define pb push_back
#define pp pop_back
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())

string pr(int* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr( ll* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr( vector<ll> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr(pii* vv,int l,int r){for(int i=l;i<r;i++)cout<<"( "<<vv[i].f<<","<<vv[i].s<<" )    ";return "";}
string pr(vector<pii> vv){for(auto i:vv)cout<<"( "<<i.f<<","<<i.s<<" )    ";return "";}

const int L = 2e5+10,mod = 1e9+7;
const int inf = 1e9+10;
int n,C;
int cnt[L],h[L],a[L],b[L],mx[L];
vector<int> adj[L];
bool mark[L];

void Find(int v,int p,int sz){
    cnt[v] = 1;
    bool ok = 1;
    for(auto u:adj[v]){
        if(!mark[u] and u != p){
            Find(u,v,sz);
            cnt[v] += cnt[u];
            ok = ok and (2*cnt[u] <= sz);
        }
    }
    ok = ok and (2*cnt[v] >= sz);
    if(ok)
        C = v;
}

void dfs(int v,int p){
    cnt[v] = 1;
    for(auto u:adj[v]){
        if(!mark[u] and u != p){
            h[u] = h[v]+1;
            dfs(u,v);
            cnt[v] += cnt[u];
        }
    }
    b[cnt[v]] = max(b[cnt[v]],h[v]);
}

void solve(int v,int sz){
    if(sz == 1)
        return;
    Find(v,0,sz);
    mark[C] = 1;
    //cout<<"C: "<<C<<endl;

    for(int i=1;i<=sz;i++){
        a[i] = b[i] = 0;
    }
    for(auto u:adj[C]){
        if(mark[u])
            continue;
        h[u] = 1;
        dfs(u,C);
        for(int i=cnt[u]-1;i>=1;i--){
            b[i] = max(b[i],b[i+1]);
        }
        //cout<<"dfs: "<<u<<" --> "<<pr(b,1,cnt[u]+1)<<endl;
        for(int i=1;i<=cnt[u];i++){
            mx[i] = max(mx[i],b[i]+a[i]);
            a[i] = max(a[i],b[i]);
            b[i] = 0;
        }
    }
    //cout<<"----------------------------"<<endl;
    for(auto u:adj[C]){
        if(!mark[u]){
            solve(u,cnt[u]);
        }
    }
}

int main(){
    //ofstream cout ("out.out");
    //ifstream cin ("in.in");

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

    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    solve(1,n);

    for(int i=n/2;i>=1;i--){
        mx[i] = max(mx[i+1],mx[i]+1);
    }
    for(int i=1;i<=n;i++){
        if(i%2)
            cout<<1<<endl;
        else
            cout<<mx[i/2]<<endl;
    }
}

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