Submission #1271264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271264		chikien2009	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	238 ms	19944 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], res[400001];
vector<int> g[200000];
bool mark[200000];

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

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

inline void Get(int node, int par, int depth, vector<int> &inp)
{
    sz[node] = 1;
    for (auto &i : g[node])
    {
        if (i != par && !mark[i])
        {
            Get(i, node, depth + 1, inp);
            sz[node] += sz[i];
        }
    }
    inp[sz[node]] = max(inp[sz[node]], depth);
}

inline void DFS(int node)
{
    int centroid;
    vector<int> cur, temp;
    Cal(node, node);
    centroid = FindCentroid(node, node, sz[node]);
    mark[centroid] = true;
    cur.resize(sz[node], 0);
    temp.resize(sz[node], -1);
    for (auto &i : g[centroid])
    {
        if (!mark[i])
        {
            Get(i, centroid, 1, temp);
            for (int j = sz[i]; j >= 1; --j)
            {
                if (j < sz[i])
                {
                    temp[j] = max(temp[j], temp[j + 1]);
                }
                if (cur[j] != -1)
                {
                    res[j * 2] = max(res[j * 2], cur[j] + temp[j]);
                }
                cur[j] = max(cur[j], temp[j]);
            }
            fill_n(temp.begin(), sz[i] + 1, -1);
        }
    }
    for (auto &i : g[centroid])
    {
        if (!mark[i])
        {
            DFS(i);
        }
    }
}

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);
    for (int i = 1; i <= n; ++i)
    {
        cout << (i & 1 ? 0 : res[i]) + 1 << "\n";
    }
    return 0;
}

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