제출 #1237207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237207		Seyyed_Mojtaba_Mortazavi	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	6 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 par = -1, int h = 1)
{
    a[sz[v]] = max(a[sz[v]], h);
	for (auto u : e[v])
    {
		if (u != par && !mark[u])
		    dfs2(a, u, v, h + 1);
	}
}

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 % 2 ? 1 : ans[i / 2]) << endl;
    }
}

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