Submission #1271126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271126		chikien2009	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	1 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);
}

inline void Combine(pair<int, int> &tar, pair<int, int> inp)
{
    tar = max({tar, inp, {tar.first, inp.first}, {inp.first, tar.first}});
}

struct SEGMENT_TREE
{
    pair<int, int> tree[800000], rem[800000];
    inline void UpdateNode(int ind, int l, int r)
    {
        Combine(tree[ind], rem[ind]);
        if (l < r)
        {
            Combine(rem[ind << 1], rem[ind]);
            Combine(rem[ind << 1 | 1], rem[ind]);
        }
        rem[ind] = {0, 0};
    }
    inline void Update(int ind, int l, int r, int x, int v)
    {
        UpdateNode(ind, l, r);
        if (x < l)
        {
            return;
        }
        if (r <= x)
        {
            rem[ind] = {v, 0};
            UpdateNode(ind, l, r);
            return;
        }
        int m = (l + r) >> 1;
        Update(ind << 1, l, m, x, v);
        Update(ind << 1 | 1, m + 1, r, x, v);
    }
    inline pair<int, int> Get(int ind, int l, int r, int x)
    {
        UpdateNode(ind, l, r);
        if (l == r)
        {
            return tree[ind];
        }
        int m = (l + r) >> 1;
        if (x <= m)
        {
            return Get(ind << 1, l, m, x);
        }
        return Get(ind << 1 | 1, m + 1, r, x);
    }
} st;

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

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);
    }
    DFS(0, 0);
    a = FindCenter(0, 0);
    fill_n(sz, n, 0);
    for (auto &i : g[a])
    {
        DFS1(i, a, 1);
        for (int j = 1; j <= sz[i]; ++j)
        {
            st.Update(1, 1, n, j, d[j]);
        }
        fill_n(d, sz[i], 0);
    }
    for (int i = 1; i * 2 <= n; ++i)
    {
        temp = st.Get(1, 1, n, i);
        res[2 * i] = temp.second + temp.first;
    }
    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