Submission #926075

#	Time	Username	Problem	Language	Result	Execution time	Memory
926075		andrei_boaca	Meetings 2 (JOI21_meetings2)	C++17	20 / 100	4043 ms	17748 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;
int n,sol[200005],par[200005],reprez[200005],niv[200005],nr[200005];
vector<int> muchii[200005];
void dfs(int nod)
{
    nr[nod]=1;
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            par[i]=nod;
            niv[i]=niv[nod]+1;
            if(reprez[nod]==0)
                reprez[i]=i;
            else
                reprez[i]=reprez[nod];
            dfs(i);
            nr[nod]+=nr[i];
        }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        sol[i]=1;
    for(int i=1;i<=n;i++)
    {
        par[i]=0;
        reprez[i]=0;
        niv[i]=1;
        dfs(i);
        for(int j=1;j<=n;j++)
            if(j!=i)
            {
                int poz=2*min(n-nr[reprez[j]],nr[j]);
                int lg=niv[j];
                sol[poz]=max(sol[poz],lg);
            }
    }
    for(int i=(n/2)*2;i>0;i-=2)
        sol[i]=max(sol[i],sol[i+2]);
    for(int i=1;i<=n;i++)
        cout<<sol[i]<<'\n';
    return 0;
}

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