Submission #1249112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249112		arashmemar	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	421 ms	29120 KiB

meetings2

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

const int maxn = 2e5 + 100;

int ans[maxn], vu[maxn], md[maxn], nmd[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 and vu[v] >= (k + 1) / 2)
	{
		ret = {h, v};
	}
	mark[v] = 0;
	return ret;
}

void dfs(int v, int h = 2)
{
	mark[v] = 1;
	nmd[vu[v]] = max(nmd[vu[v]], h);
	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		dfs(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] = 1;
	}
	mark[v] = 1;

	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		for (int i = vu[u];i;i--)
		{
			nmd[i] = 2;
		}
		nmd[vu[u] + 1] = 0;
		dfs(u);
		for (int i = vu[u];i;i--)
		{
			nmd[i] = max(nmd[i], nmd[i + 1]);
			ans[i] = max(ans[i], nmd[i] + md[i] - 1);
			md[i] = max(md[i], nmd[i]);
		}
	}
	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		solve(u, vu[u]);
	}
	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: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80