제출 #496230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496230		Rainbowbunny	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	821 ms	26772 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;

int n;
int sz[MAXN], ans[MAXN], H[MAXN], nw[MAXN];
bool Mark[MAXN];
vector <int> Adj[MAXN];

void DFS(int node, int p)
{
    sz[node] = 1;
    for(auto x : Adj[node])
    {
        if(x == p or Mark[x])
        {
            continue;
        }
        DFS(x, node);
        sz[node] += sz[x];
    }
}

int FindCen(int node, int p, int cursz)
{
    for(auto x : Adj[node])
    {
        if(x == p or Mark[x])
        {
            continue;
        }
        if(2 * sz[x] > cursz)
        {
            return FindCen(x, node, cursz);
        }
    }
    return node;
}

vector <int> Cur;

void Cal(int node, int p)
{
    sz[node] = 1;
    for(auto x : Adj[node])
    {
        if(x == p or Mark[x])
        {
            continue;
        }
        H[x] = H[node] + 1;
        Cal(x, node);
        sz[node] += sz[x];
    }
    if(Cur.empty() or Cur[0] < sz[node])
    {
        // do nothing
    }
    else
    {
        int id = upper_bound(Cur.begin(), Cur.end(), sz[node], greater <int> ()) - Cur.begin() - 1;
        assert(id >= 0);
        ans[2 * sz[node]] = max(ans[2 * sz[node]], H[node] + id + 3);
    }
    nw[H[node]] = max(nw[H[node]], sz[node]);
}

void Cal2(int node, int p, int s)
{
    for(auto x : Adj[node])
    {
        if(x == p or Mark[x])
        {
            continue;
        }
        Cal2(x, node, s);
    }
    if(Cur.empty() or Cur[0] < sz[node])
    {
        // do nothing
    }
    else
    {
        int id = upper_bound(Cur.begin(), Cur.end(), sz[node], greater <int> ()) - Cur.begin() - 1;
        assert(id >= 0);
        ans[2 * sz[node]] = max(ans[2 * sz[node]], H[node] + id + 3);
    }
    nw[H[node]] = max(nw[H[node]], sz[node]);
    ans[2 * min(s, sz[node])] = max(ans[2 * min(s, sz[node])], H[node] + 2);
}

void Solve(int node, int p)
{
    DFS(node, p);
    int cen = FindCen(node, p, sz[node]);
    Mark[cen] = true;
    Cur.clear();
    int ss = sz[node];
    for(auto x : Adj[cen])
    {
        H[x] = 0;
        if(Mark[x])
        {
            continue;
        }
        Cal(x, cen);
        for(int i = 0; ; i++)
        {
            if(nw[i] == 0)
            {
                break;
            }
            if(i < (int)Cur.size())
            {
                Cur[i] = max(Cur[i], nw[i]);
            }
            else
            {
                Cur.push_back(nw[i]);
            }
            nw[i] = 0;
        }
    }
    Cur.clear();
    reverse(Adj[cen].begin(), Adj[cen].end());
    for(auto x : Adj[cen])
    {
        H[x] = 0;
        if(Mark[x])
        {
            continue;
        }
        Cal2(x, cen, ss - sz[x]);
        for(int i = 0; ; i++)
        {
            if(nw[i] == 0)
            {
                break;
            }
            if(i < (int)Cur.size())
            {
                Cur[i] = max(Cur[i], nw[i]);
            }
            else
            {
                Cur.push_back(nw[i]);
            }
            nw[i] = 0;
        }
    }
    for(auto x : Adj[cen])
    {
        if(!Mark[x])
        {
            Solve(x, cen);
        }
    }
}

int main()
{
    // freopen("Input.txt", "r", stdin);
    // freopen("Output2.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        Adj[u].push_back(v);
        Adj[v].push_back(u);
    }

    Solve(1, -1);
    for(int i = n; i >= 1; i--)
    {
        ans[i] = max(ans[i], ans[i + 1]);
    }

    for(int i = 1; i <= n; i++)
    {
        if(i & 1)
        {
            cout << 1 << '\n';
        }
        else
        {
            cout << max(ans[i], 1) << '\n';
        }
    }
}

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