Submission #1249064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249064		arashmemar	Capital City (JOI20_capital_city)	C++20	0 / 100	114 ms	13252 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 100;

int ans[maxn], vu[maxn], md[maxn];
bool mark[maxn];
vector <int> ne[maxn];

pair <int, int> find(int v, int k, int h = 0)
{
	mark[v] = 1;
	vu[v] = 1;
	pair <int, int> ret = {maxn, maxn};
	bool ok = 1;
	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		ret = min(ret, find(u, k, h + 1));
		vu[v] += vu[u];
		if (vu[u] > k / 2)
		{
			ok = 0;
		}
	}
	if (ok)
	{
		ret = {h, v};
	}
	mark[v] = 0;
	return ret;
}

int co;

void dfs(int v, int h = 2)
{
	mark[v] = 1;
	ans[min(co, vu[v])] = max(ans[min(co, vu[v])], h);
	ans[vu[v]] = max(ans[vu[v]], h + md[vu[v]] - 1);
	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		dfs(u, h + 1);
	}
	mark[v] = 0;
	return ;
}

void upd(int v, int h = 2)
{
	mark[v] = 1;
	md[vu[v]] = max(md[vu[v]], h);
	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		upd(u, h + 1);
	}
	mark[v] = 0;
	return ;
}

void solve(int v, int s)
{
	if (s == 1)
	{
		return ;
	}
	v = find(v, s).second;
	find(v, 0);
	for (int i = 1;i <= s;i++)
	{
		md[i] = -maxn;
	}
	mark[v] = 1;

	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		co = vu[v] - vu[u];
		dfs(u);
		upd(u);
		for (int i = vu[u];i;i--)
		{
			md[i] = max(md[i], md[i + 1]);
		}
	}
	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		solve(u, vu[u]);
	}
	mark[v] = 0;
	return ;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1;i < n;i++)
	{
		int v, u;
		cin >> v >> u;
		ne[v].push_back(u);
		ne[u].push_back(v);
	}
	solve(1, n);

	for (int i = n;i;i--)
	{
		ans[i] = max(ans[i], ans[i + 1]);
	}

	for (int i = 1;i <= n;i++)
	{
		if (i % 2)
		{
			cout << 1 << ' ';
		}
		else
		{
			cout << max(ans[i / 2], 1) << ' ';
		}
	}
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59