Submission #538510

#	Time	Username	Problem	Language	Result	Execution time	Memory
538510		pavement	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	636 ms	68556 KiB

meetings2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, cur, root, dep[200005], sz[200005], ans[200005], anc[200005][25];
ii T[200005];
vector<int> adj[200005];

int dfs(int n, int e = -1) {
	int s = 1, m = 0;
	for (auto u : adj[n]) if (u != e) {
		int tmp = dfs(u, n);
		s += tmp;
		m = max(m, tmp);
	}
	m = max(m, N - s);
	if (m <= N / 2) root = n;
	return s;
}

int init(int n, int e = -1) {
	anc[n][0] = e;
	sz[n] = 1;
	for (auto u : adj[n]) if (u != e) {
		dep[u] = dep[n] + 1;
		sz[n] += init(u, n);
	}
	return sz[n];
}

int lca(int u, int v) {
	if (dep[u] > dep[v]) swap(u, v);
	for (int i = 20; i >= 0; i--)
		if (anc[v][i] != -1 && dep[anc[v][i]] >= dep[u]) v = anc[v][i];
	if (u == v) return u;
	for (int i = 20; i >= 0; i--)
		if (anc[u][i] != -1 && anc[v][i] != -1 && anc[u][i] != anc[v][i]) {
			u = anc[u][i];
			v = anc[v][i];
		}
	return anc[u][0];
}

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

main() {
	memset(anc, -1, sizeof anc);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1, u, v; i < N; i++) {
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1);
	assert(root);
	init(root);
	for (int k = 1; k <= 20; k++)
		for (int i = 1; i <= N; i++)
			if (anc[i][k - 1] != -1) anc[i][k] = anc[anc[i][k - 1]][k - 1];
	for (int i = 1; i <= N; i++) T[i] = mp(sz[i], i);
	sort(T + 1, T + 1 + N, greater<ii>());
	for (int i = 1, ed1, ed2; i <= N; i++) {
		if (i == 1) {
			ed1 = ed2 = T[i].second;
			ans[T[i].first] = max(ans[T[i].first], 1ll);
			continue;
		}
		iii tmp = max({mt(dist(ed1, ed2), ed1, ed2), mt(dist(ed1, T[i].second), ed1, T[i].second), mt(dist(ed2, T[i].second), ed2, T[i].second)});
		ed1 = g1(tmp);
		ed2 = g2(tmp);
		ans[T[i].first] = max(ans[T[i].first], g0(tmp) + 1);
	}
	for (int i = N; i >= 1; i--) ans[i] = max(ans[i], ans[i + 1]);
	for (int i = 1; i <= N; i++)
		if (i & 1) cout << "1\n";
		else cout << ans[i / 2] << '\n';
}

Compilation message (stderr)

meetings2.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main() {
      | ^~~~

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