Submission #1294560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294560		vivkostov	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	2 ms	572 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n,a[200005],b[200005],used[200005],lead,bot,path[200005],p[200005],otg[200005],mid,use[200005],ind[200005],mid1,mid2;
vector<int>v[200005],dp[200005];
void bfs(int beg)
{
    used[beg]=1;
    int w,nb;
    queue<int>q;
    q.push(beg);
    while(q.size())
    {
        w=q.front();
        q.pop();
        for(int i=0;i<v[w].size();i++)
        {
            nb=v[w][i];
            if(!used[nb])
            {
                q.push(nb);
                used[nb]=used[w]+1;
            }
        }
    }
}
void clea(int beg,int par)
{
    used[beg]=0;
    int w;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(w==par||!used[w])continue;
        clea(w,beg);
    }
}
void prec()
{
    int to=bot,nex,par=0;
    while(to!=lead)
    {
        for(int i=0;i<v[to].size();i++)
        {
            if(v[to][i]==par)continue;
            if(used[v[to][i]]!=used[to]-1)
            {
                used[v[to][i]]=0;
                clea(v[to][i],to);
            }
            else nex=v[to][i];
        }
        par=to;
        to=nex;
    }
}
void calc(int beg,int lead,int par)
{
    int w;
    p[lead]++;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!used[w]&&w!=par)
        {
            calc(w,lead,beg);
        }
    }
}
int check(int mi)
{
    int br=0;
    for(int i=1;i<=n;i++)
    {
        if(used[i]&&used[i]<=mi)br+=p[i];
    }
    return br;
}
void find_mid()
{
    int l=1,r=used[bot],mi;
    while(l<=r)
    {
        mi=(l+r)/2;
        //cout<<check(mi)<<" "<<l<<" "<<r<<endl;
        if(check(mi)>n/2)r=mi-1;
        else l=mi+1;
    }
    mid2=l;
    if(check(l-1)>=check(l+1))
    {
        mid1=l-1;
    }
    else mid1=l+1;
    for(int i=1;i<=n;i++)
    {
        if(used[i]==mid1)
        {
            mid1=i;
            break;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(used[i]==mid2)
        {
            mid2=i;
            break;
        }
    }
}
void get_dp(int beg,int par,int level)
{
    int w;
    //cout<<beg<<" "<<par<<endl;
    if(v[beg].size()==1)
    {
        ind[beg]=beg;
        dp[beg].push_back(level);
        return;
    }
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(w==par)continue;

        get_dp(w,beg,level+1);
        if(dp[ind[beg]].size()<dp[ind[w]].size())
        {
            ind[beg]=ind[w];
        }
    }
    int sum=1;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(w==par||ind[w]==ind[beg])continue;
        sum+=dp[ind[w]].size();
        for(int j=0;j<dp[ind[w]].size();j++)
        {
            dp[ind[beg]][j]=max(dp[ind[beg]][j],dp[ind[w]][j]);
        }
    }
    for(int i=0;i<sum;i++)
    {
        dp[ind[beg]].push_back(level);
    }
}
void read()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>a[i]>>b[i];
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }
    cout<<endl<<endl;
    bfs(1);
    int ma=0;
    for(int i=1;i<=n;i++)
    {
        if(ma<used[i])
        {
            ma=used[i];
            lead=i;
        }
        used[i]=0;
    }
    bfs(lead);
    ma=0;
    for(int i=1;i<=n;i++)
    {
        if(ma<used[i])
        {
            ma=used[i];
            bot=i;
        }
    }
    prec();
    for(int i=1;i<=n;i++)
    {
        if(used[i])calc(i,i,0);
    }
    find_mid();
    get_dp(mid1,mid2,1);
    get_dp(mid2,mid1,1);
    //cout<<lead<<" "<<bot<<endl;
    //cout<<mid1<<" "<<mid2<<endl;
    /*for(int i=1;i<=n;i++)
    {
        cout<<i<<" : ";
        for(int j=0;j<dp[ind[i]].size();j++)
        {
            cout<<dp[ind[i]][j]<<" ";
        }
        cout<<endl;
    }*/
    for(int i=1;i<=n;i++)
    {
        if(i%2==1)cout<<1<<" ";
        else
        {
            //cout<<min(dp[ind[mid1]].size(),dp[ind[mid2]].size())<<n/2-1<<endl;
            if(min(dp[ind[mid1]].size(),dp[ind[mid2]].size())>i/2-1)cout<<dp[ind[mid1]][i/2-1]+dp[ind[mid2]][i/2-1]<<" ";
            else cout<<1<<" ";
        }
    }
    cout<<endl;
}
int main()
{
    speed();
    read();
}

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