oj.uz

Submission #404822

# Submission time Handle Problem Language Result Execution time Memory
404822 2021-05-15T05:37:45 Z dvdg6566 Meetings 2 (JOI21_meetings2) C++14
0 / 100
 3 ms 4940 KB 
#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=200100;
const ll MAXK = 19;

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];

struct CentDecomp{
    vi par,ban,sub;
    ll d[MAXN][MAXK];
    ll N;

    CentDecomp(ll _N):N(_N){
        par.resize(N+1,0);
        ban.resize(N+1,0);
        sub.resize(N+1,0);
    }
    void build(ll x,ll p,ll l){
        if(l)d[x][l-1]=1;
        ll n=dfs(x,p,l);
        ll cent=dfs2(x,p,n);
        par[cent]=p;
        ban[cent]=l;
        for(auto v:V[cent]){
            if(ban[v]==0)build(v,x,l+1);
        }
    }

    ll dfs(ll x,ll p,ll l){
        sub[x]=1;
        for(auto v:V[x])if(ban[v]==0&&v!=p){
            if(l)d[v][l-1]=d[x][l-1]+1;
            sub[x]+=dfs(v,x,l);
        }
        return sub[x];
    }
    ll dfs2(ll x,ll p,ll n){
        for(auto v:V[x])if(ban[v]==0&&v!=p&&sub[v]>n/2){
            return dfs2(v,x,n);
        }
        return x;
    }
}*G;

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);
}

ll cd[MAXN];

void addNode(ll x){
    // cerr<<"ADD "<<x<<'\n';
    ll l=G->ban[x];
    ll p=x;
    while(l>=1){
        ll t=cd[p]+G->d[x][l];
        ans=max(ans,t);
        --l;
        p=G->par[p];
    }

    l=G->ban[x];p=x;
    while(l>=1){
        cd[p]=max(cd[p],G->d[x][l]);
        // cerr<<"Upd "<<p<<' '<<cd[p]<<'\n';
        --l;
        p=G->par[p];
    }
}

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));
    
    G=new CentDecomp(N);
    G->build(1,-1,1);
    // for(int i=1;i<=N;++i)cerr<<i<<' '<<G->ban[i]<<' '<<G->par[i]<<'\n';

    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();
            addNode(t.s);
            // A[t.s]=1;
            // cerr<<"Adding "<<t.s<<'\n';
            // dfs2(t.s,1,-1);
        }
        out[i]=ans+1;
    }
    for(ll i=1;i<=N;++i)cd[i]=-1e9;
    for(ll i=1;i<=N;++i){
        if(i%2)cout<<1<<'\n';
        else cout<<out[i]<<'\n';
    }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 3 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 3 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 3 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -