Submission #404839

#	Time	Username	Problem	Language	Result	Execution time	Memory
404839		dvdg6566	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	755 ms	53288 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=200100;
const int MAXK=19;
 
ll N,a,b,c,Q;
vi V[MAXN];
ll sub[MAXN];
ll small[MAXN];
ll A[MAXN];
ll out[MAXN];
int p[MAXN][MAXK];
int d[MAXN];
 
ll dfs(ll x,ll pa){
    sub[x]=1;
    p[x][0]=pa;
    if(pa!=-1)d[x]=d[pa]+1;
    for(int i=1;i<MAXK;++i){
        if(p[x][i-1]!=-1)p[x][i]=p[p[x][i-1]][i-1];
    }
    for(auto v:V[x])if(v!=pa)sub[x]+=dfs(v,x);
    return sub[x];
}
 
set<pi> S;

int lca(int a,int b){
    if(a==b)return a;
    if(d[a]>d[b])swap(a,b); // d[a] < d[b]
    int hd=d[b]-d[a];
    for(int i=0;i<MAXK;++i)if((1<<i)&hd){
        b=p[b][i];
    }
    if(a==b)return a;
    for(int i=MAXK-1;i>=0;--i){
        if(p[a][i]!=p[b][i]){a=p[a][i];b=p[b][i];}
    }
    assert(p[a][0]==p[b][0]);
    return p[a][0];
}

int fd(int x,int y){
    return d[x]+d[y]-2*d[lca(x,y)]+1;
}

pi T;
int ans;

void addNode(int x){
    // cerr<<"Add "<<x<<'\n';
    if(T.f==-1){
        T=mp(x,x);
        ans=1;
    }else{
        int a=fd(x,T.f);
        int b=fd(x,T.s);
        int c=fd(T.f,T.s);
        if(a>=c&&a>=b){
            T=mp(x,T.f);
        }else if(b>=a&&b>=c){
            T=mp(x,T.s);
        }else{
            T=mp(T.f,T.s);
        }
        ans=fd(T.f,T.s);
    }
    assert(!A[x]);
    A[x]=1;
    for(auto v:V[x])if(!A[v]){
        S.insert(mp(small[v],v));
    }
    // for(int i=1;i<=N;++i)if(A[i]){
    //     if(fd(x,i)>ans){
    //         cerr<<"TRY "<<x<<' '<<i<<' '<<ans<<'\n';
    //         cerr<<"ANS "<<T.f<<' '<<T.s<<'\n';
    //         assert(0);
    //     }
    // }
}
 
int main(){
    T=mp(-1,-1);
    memset(p,-1,sizeof(p));
    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][0]){
            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));
    S.insert(nodes.back());
 
    for(ll i=(N/2)*2; i>=2;i-=2){
        // cerr<<"At "<<i<<'\n';
        while(SZ(S)){
            pi t=*(--S.end());
            if(t.f<i/2)break;
            S.erase(--S.end());
            addNode(t.s);
        }
        // cerr<<ans<<'\n';
        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: 80 / 80