Submission #1086055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086055		ymm	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	198 ms	42696 KiB

meetings2

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
const int lg = 20;
vector<int> A[N];
int sub[N];
int anc[N][lg];
int height[N];
int n;

int ans[N];

void dfs1(int v, int p, int h)
{
	sub[v] = 1;
	height[v] = h;
	for (int u : A[v]) {
		if (u == p)
			continue;
		dfs1(u, v, h+1);
		sub[v] += sub[u];
	}
}

void dfs2(int v, int p, int h)
{
	sub[v] = 1;
	height[v] = h;
	anc[v][0] = p;
	Loop (i,0,lg-1)
		anc[v][i+1] = anc[anc[v][i]][i];
	for (int u : A[v]) {
		if (u == p)
			continue;
		dfs2(u, v, h+1);
		sub[v] += sub[u];
	}
}

int lca(int v, int u)
{
	if (height[v] < height[u])
		swap(v, u);
	int diff = height[v] - height[u];
	Loop (i,0,lg)
		if ((diff>>i)&1)
			v = anc[v][i];
	if (v == u)
		return v;
	LoopR (i,0,lg) {
		if (anc[v][i] != anc[u][i]) {
			v = anc[v][i];
			u = anc[u][i];
		}
	}
	return anc[v][0];
}

int dis(int v, int u)
{
	return height[v] + height[u] - 2 * height[lca(v, u)];
}

int centroid(int v, int p)
{
	for (int u : A[v]) {
		if (u != p && sub[u] * 2 > n)
			return centroid(u, v);
	}
	return v;
}

void solve(int rt)
{
	int v = rt, u = rt;
	priority_queue<pair<int, int>> pq;
	Loop (i,0,n)
		pq.emplace(sub[i], i);
	int d = 0;
	while (pq.size()) {
		auto [sz, w] = pq.top();
		pq.pop();
		int wv = dis(w, v);
		int wu = dis(w, u);
		if (wv > d) {
			d = wv;
			u = w;
		} else if (wu > d) {
			v = w;
			d = wu;
		}
		ans[sz] = max(ans[sz], d + 1);
	}
	LoopR (i,0,n)
		ans[i] = max(ans[i], ans[i+1]);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A[v].push_back(u);
		A[u].push_back(v);
	}
	dfs1(0, 0, 0);
	int rt = centroid(0, -1);
	dfs2(rt, rt, 0);
	solve(rt);
	Loop (i,1,n+1) {
		if (i%2 == 1)
			cout << "1\n";
		else
			cout << ans[i/2] << '\n';
	}
}

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