Submission #1294525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294525		Ice_man	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	433 ms	30864 KiB

meetings2

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <bits/stdc++.h>



#define maxn (int)(1e6 + 10)
#define PB push_back
#define X first
#define Y second


typedef long long ll;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
typedef std::pair <int, ll> pil;
typedef std::pair <ll, int> pli;

const ll mod = 1e9 + 7;
const ll INF = 1e9;



std::vector <int> v[maxn];
int sz[maxn], par[maxn], op[maxn];
int osz[maxn];
int nn;

void precalc(int node, int pp)
{
    osz[node] = 1;

    for(auto& nb : v[node])
    {
        if(pp == nb)
            continue;

        op[nb] = node;
        precalc(nb, node);

        osz[node] += osz[nb];
    }
}



bool used[maxn];

void calc_sz(int node, std::vector <int>& curr)
{
    used[node] = true;
    sz[node] = 1;

    curr.PB(node);

    for(auto& nb : v[node])
    {
        if(used[nb] == true)
            continue;

        calc_sz(nb , curr);
        sz[node] += sz[nb];
    }
}


int dist[maxn];
int up[maxn];

void calc_up(int node, int u)
{
    used[node] = true;
    up[node] = u;

    for(auto& nb : v[node])
    {
        if(used[nb] == true)
            continue;

        dist[nb] = dist[node] + 1;
        par[nb] = node;

        calc_up(nb, u);
    }
}




int ans[maxn];



void decompose(int start)
{
    std::vector <int> curr;
    calc_sz(start, curr);

    int n = curr.size();
    int cent = -1;
    for(auto& e : curr)
    {
        bool lamp = true;
        if(n - sz[e] > n / 2)
            continue;

        for(auto& nb : v[e])
            if(sz[nb] < sz[e] && sz[nb] > n / 2)
                lamp = false;

        if(lamp == true)
        {
            cent = e;
            break;
        }
    }


    for(auto& e : curr)
        used[e] = false;

    used[cent] = true;
    par[cent] = -1;
    up[cent] = -1;
    dist[cent] = 0;

    for(auto& nb : v[cent])
    {
        par[nb] = cent;
        dist[nb] = 1;

        calc_up(nb, nb);
    }


    std::vector <pii> cc;
    for(auto& e : curr)
        if(e != cent)
        {
            if(par[e] == op[e])
                cc.PB({osz[e], e});
            else
                cc.PB({nn - osz[par[e]], e});
        }

    std::sort(cc.begin(), cc.end());
    std::reverse(cc.begin(), cc.end());

    pii maxx1 = {0, cent}, maxx2 = {0, cent};

    for(auto& e : cc)
    {
        int val = e.X;
        int node = e.Y;

        if(maxx1.Y != up[node])
            ans[val] = std::max(maxx1.X + dist[node] + 1, ans[val]);
        else
            ans[val] = std::max(maxx2.X + dist[node] + 1, ans[val]);


        if(maxx1.Y == up[node])
            maxx1.X = std::max(dist[node], maxx1.X);
        else if(maxx2.Y == up[node])
            maxx2.X = std::max(dist[node], maxx2.X);
        else if(dist[node] > maxx2.X)
            maxx2 = {dist[node], up[node]};


        if(maxx1.X < maxx2.X)
            std::swap(maxx1, maxx2);
    }


    for(auto& e : curr)
        used[e] = false;
    for(auto& nb : v[cent])
    {
        v[nb].erase(std::find(v[nb].begin() , v[nb].end() , cent));
        decompose(nb);
    }


}



void read()
{
    std::cin >> nn;

    for(int i = 0; i < nn - 1; i++)
    {
        int a , b;
        std::cin >> a >> b;

        v[a].PB(b);
        v[b].PB(a);
    }

    op[1] = -1;
    precalc(1 , -1);

    for(int i = 1; i <= nn; i++)
        ans[i] = 1;

    for(int i = 1; i <= nn; i++)
        used[i] = false;

    decompose(1);
    int maxx = 1;

    for(int i = nn / 2 - 1; i >= 1; i--)
        ans[i] = std::max(ans[i] , ans[i + 1]);

    for(int i = 1; i <= nn; i++)
    {
        if(i % 2 == 1)
        {
            std::cout << 1 << "\n";
            continue;
        }

        std::cout << ans[i / 2] << "\n";
    }
}






int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int tests = 1;

    //std::cin >> tests;
    while(tests--)
    {
        read();
    }



    return 0;
}

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