제출 #1237196

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237196		Seyyed_Mojtaba_Mortazavi	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	7 ms	12104 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9 + 10;
const int MAXN = 5e5 + 10;

int sz[MAXN];
int ans[MAXN];
bool mark[MAXN];
vector <int> e[MAXN];

void dfs(int n, int &cent, int v, int par = -1)
{
    sz[v] = 1;
    for (auto u : e[v])
    {
        if (u != par && !mark[u])
        {
            dfs(n, cent, u, v);
            sz[v] += sz[u];
        }
    }
    if (sz[v] >= n && (cent == -1 || sz[v] < sz[cent]))
        cent = v;
}

void dfs2(vector <int> &a, int v, int h = 1, int par = -1)
{
    a[sz[v]] = max(a[sz[v]], h);
    for (auto u : e[v])
    {
        if (u != par && !mark[u])
            dfs2(a, u, h + 1, v);
    }
}

void Centroid(int root, int n)
{
    if (n == 1)
        return;
    int cent = -1;
    dfs((n + 1) / 2, cent, root);
    dfs(0, root, cent);
    mark[cent] = true;
    vector <int> b(sz[cent] + 1, -INF);
    for (auto u : e[cent])
    {
        if (!mark[u])
        {
            vector <int> a(sz[u] + 1, -INF);
            dfs2(a, u);
            for (int i = sz[u] - 1; i >= 1; i--)
                a[i] = max(a[i], a[i + 1]);
            for (int i = 1; i <= sz[u]; i++)
            {
                ans[i] = max(ans[i], a[i] + b[i] + 1);
                b[i] = max(b[i], a[i]);
                if (i <= n - sz[u])
                    ans[i] = max(ans[i], b[i] + 1);
            }
        }
    }
    for (auto u : e[cent])
    {
        if (!mark[u])
            Centroid(u, sz[u]);
    }
}

signed main()
{
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int v, u;
        cin >> v >> u;
        e[v].push_back(u);
        e[u].push_back(v);
    }
    Centroid(1, n);
    for (int i = 1; i <= n; i++)
        cout << (i & 1 ? 1 : ans[i / 2]) << endl;
    return 0;
}

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