Submission #396095

#	Time	Username	Problem	Language	Result	Execution time	Memory
396095		Mlxa	Meetings 2 (JOI21_meetings2)	C++17	20 / 100	4094 ms	19692 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#define int ll

const int N = 2e5 + 10;
const int INF = 1e18;

int n;
vector<int> g[N];
int down[N], value[N];

void dfs(int v, int p) {
	down[v] = 1;
	vector<int> sons;
	for (int u : g[v]) {
		if (u == p) {
			continue;
		}
		dfs(u, v);
		down[v] += down[u];
		sons.push_back(down[u]);
	}
	sons.push_back(n - down[v]);
	value[v] = n - *max_element(all(sons));
}

int dist[N];

int bfs(int from, int lim) {
	assert(value[from] >= lim);
	queue<int> q;
	fill_n(dist, N, INF);
	dist[from] = 1;
	q.push(from);
	int v = from;
	while (q.size()) {
		v = q.front(); q.pop();
		for (int u : g[v]) {
			if (value[u] >= lim && dist[u] > dist[v] + 1) {
				dist[u] = dist[v] + 1;
				q.push(u);
			}
		}
	}
	return v;
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	for (int v, u, i = 0; i < n - 1; ++i) {
		cin >> v >> u;
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	dfs(0, 0);
	int start = (int)(max_element(value, value + n) - value);
	for (int i = 1; i <= n; ++i) {
		if (i % 2) {
			cout << "1\n";
			continue;
		}
		int v = bfs(start, i / 2);
		v = bfs(v, i / 2);
		cout << dist[v] << "\n";
	}
	return 0;
}

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