Submission #1294521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294521		vivkostov	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	2 ms	716 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];
vector<int>v[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);
        }
    }
}
void resh()
{
    int l=lead,r=bot;
    for(int i=2;i<=n;i+=2)
    {
        p[l]--;
        p[r]--;
        otg[i]=used[r]-used[l]+1;
        if(!p[l])
        {
            for(int i=0;i<v[l].size();i++)
            {
                if(used[v[l][i]]==used[l]+1)
                {
                    l=v[l][i];
                    break;
                }
            }
        }
        if(!p[r])
        {
            for(int i=0;i<v[r].size();i++)
            {
                if(used[v[r][i]]==used[r]-1)
                {
                    r=v[r][i];
                    break;
                }
            }
        }
    }
}
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]);
    }
    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);
    }
    resh();
    for(int i=1;i<=n;i++)
    {
        if(i%2==1)cout<<1<<" ";
        else cout<<otg[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    speed();
    read();
}

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