Submission #1271163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271163		chikien2009	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	2 ms	328 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, a, b;
int sz[200000], d[200000], res[200001];
vector<int> g[200000], v[200000];

inline int Deep(int node, int par)
{
    int cur = node, temp;
    for (auto &i : g[node])
    {
        if (i != par)
        {
            d[i] = d[node] + 1;
            temp = Deep(i, node);
            if (d[temp] > d[cur])
            {
                cur = temp;
            }
        }
    }
    return cur;
}

inline void DFS(int node, int par)
{
    sz[node] = 1;
    for (auto &i : g[node])
    {
        if (i != par)
        {
            DFS(i, node);
            sz[node] += sz[i];
        }
    }
}

inline int FindCenter(int node, int par)
{
    for (auto &i : g[node])
    {
        if (i != par && sz[i] * 2 > n)
        {
            return FindCenter(i, node);
        }
    }
    return node;
}

inline void DFS1(int node, int par, int depth)
{
    sz[node] = 1;
    for (auto &i : g[node])
    {
        if (i != par)
        {
            DFS1(i, node, depth + 1);
            sz[node] += sz[i];
        }
    }
    d[sz[node]] = max(d[sz[node]], depth);
}

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    b = Deep(0, 0);
    DFS(b, b);
    a = FindCenter(b, b);
    fill_n(sz, n, 0);
    fill_n(d, n, 0);
    for (auto &i : g[a])
    {
        DFS1(i, a, 1);
        for (int j = sz[i] - 1; j >= 0; --j)
        {
            d[j] = max(d[j], d[j + 1]);
        }
        for (int j = 1; j <= sz[i]; ++j)
        {
            v[j].push_back(d[j]);
        }
        fill_n(d, sz[i], 0);
    }
    for (int i = 1; i * 2 <= n; ++i)
    {
        while (v[i].size() < 2)
        {
            v[i].push_back(0);
        }
        sort(v[i].begin(), v[i].end(), greater<int>());
        res[2 * i] = v[i][0] + v[i][1];
    }
    for (int i = 1; i <= n; ++i)
    {
        cout << res[i] + 1 << "\n";
    }
    return 0;
}

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