Submission #396108

#	Time	Username	Problem	Language	Result	Execution time	Memory
396108		Mlxa	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	350 ms	128460 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 L = 19;
const int N = 1 << 19;
const int INF = 1e18;

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

int tl[N], tr[N], ti = 0;
int st[L][N];
int l2[N];
int hei[N];
int saved[N];

int argmin(int i, int j) {
	return tl[i] < tl[j] ? i : j;
}

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

int lca(int v, int u) {
	int l = min(tl[v], tl[u]);
	int r = max(tl[v], tl[u]) + 1;
	int i = l2[r - l];
	return argmin(st[i][l], st[i][r - (1 << i)]);
}
int dist(int v, int u) {
	int l = lca(v, u);
	return hei[v] + hei[u] - 2 * hei[l];
}

int dv = -1, du = -1;

int add(int v) {
	// cout << "add " << v + 1 << endl;
	if (dv == -1) {
		dv = v;
		du = v;
		return 1;
	}
	if (dist(v, dv) < dist(v, du)) {
		swap(dv, du);
	}
	if (dist(v, dv) > dist(du, dv)) {
		du = v;
	}
	// cout << dv + 1 << " " << du + 1 << "\t" << dist(dv, du) + 1 << endl;
	return dist(dv, du) + 1;
}

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);
	for (int i = 2; i < N; ++i) {
		l2[i] = l2[i / 2] + 1;
	}
	for (int i = 1; i < L; ++i) {
		for (int j = 0; j + (1 << i) <= N; ++j) {
			st[i][j] = argmin(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
		}
	}
	vector<pair<int, int>> order;
	for (int i = 0; i < n; ++i) {
		order.emplace_back(value[i], i);
	}
	sort(order.rbegin(), order.rend());
	for (auto e : order) {
		int cd = add(e.y);
		// cout << "upd " << e.x << " " << cd << endl;
		saved[e.x] = max(saved[e.x], cd);
	}
	for (int i = N - 2; i >= 0; --i) {
		saved[i] = max(saved[i], saved[i + 1]);
	}
	for (int i = 1; i <= n; ++i) {
		if (i % 2) {
			cout << "1\n";
		} else {
			cout << saved[i / 2] << "\n";
		}
	}
	return 0;
}

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