Submission #404818

#	Time	Username	Problem	Language	Result	Execution time	Memory
404818		dvdg6566	Meetings 2 (JOI21_meetings2)	C++14	20 / 100	284 ms	1092 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define f first 
#define s second
#define mp make_pair
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound

const ll MAXN=5010;

ll N,a,b,c,d,Q;
vi V[MAXN];
ll ans;
ll p[MAXN];
ll sub[MAXN];
ll small[MAXN];
ll A[MAXN];
ll out[MAXN];

ll dfs(ll x,ll pa){
    sub[x]=1;
    p[x]=pa;
    for(auto v:V[x])if(v!=pa)sub[x]+=dfs(v,x);
    return sub[x];
}

void dfs2(ll x,ll d,ll pa){
    if(A[x])ans=max(ans,d);
    for(auto v:V[x])if(v!=pa)dfs2(v,d+1,x);
}

int main(){
    cin>>N;
    for(ll i=1;i<N;++i){
        cin>>a>>b;
        V[a].pb(b);
        V[b].pb(a);
    }    
    dfs(1,-1);
    for(ll i=1;i<=N;++i){
        b=N-sub[i];
        for(auto j:V[i])if(j!=p[i]){
            b=max(b,sub[j]);
        }
        small[i]=N-b; // everything except biggest subtree
    }
    // for(ll i=1;i<=N;++i)cerr<<small[i]<<' ';cerr<<'\n';
    vpi nodes;
    for(ll i=1;i<=N;++i)nodes.pb(small[i],i);
    sort(ALL(nodes));

    for(ll i=(N/2)*2; i>=2;i-=2){
        while(SZ(nodes)&&nodes.back().f>=i/2){
            pi t=nodes.back();nodes.pop_back();
            A[t.s]=1;
            // cerr<<"Adding "<<t.s<<'\n';
            dfs2(t.s,1,-1);
        }
        out[i]=ans;
    }
    for(int i=1;i<=N;++i){
        if(i%2)cout<<1<<'\n';
        else cout<<out[i]<<'\n';
    }
}

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