Submission #672467

#	Time	Username	Problem	Language	Result	Execution time	Memory
672467		flappybird	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	8 ms	14500 KiB

meetings2

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000010
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define fmax(x, a) (x) = (max((x), (a)))
int N;
vector<int> adj[MAX];
int num[MAX];
int popv[MAX];
set<pii> st[MAX];
int dep[MAX];
int ans[MAX];
void dfs(int x, int p = 0, int d = 1) {
	num[x] = 1, dep[x] = d;
	for (auto v : adj[x]) if (v != p) dfs(v, x, d + 1), num[x] += num[v];
}
void add(int sub, int d, int x) {
	auto it = st[x].lower_bound(pii(sub, 0));
	if (it != st[x].end() && it->second > d) return;
	while (1) {
		auto it = st[x].lower_bound(pii(sub + 1, 0));
		if (it == st[x].begin()) break;
		it--;
		if (it->second <= d) st[x].erase(it);
		else break;
	}
	st[x].emplace(sub, d);
}
void calc(int x, int p = 0) {
	for (auto v : adj[x]) {
		if (v == p) continue;
		calc(v, x);
		int upst = N - num[v];
		fmax(ans[upst], popv[v] - dep[x]);
		while (st[v].size() && st[v].rbegin()->first >= upst) {
			fmax(ans[upst], st[v].rbegin()->second - dep[x]);
			fmax(ans[st[v].rbegin()->first], st[v].rbegin()->second - dep[x] - 1);
			fmax(popv[x], st[v].rbegin()->second);
			st[v].erase(*st[v].rbegin());
		}
		if (st[x].size() < st[v].size()) swap(st[v], st[x]);
		for (auto& [subt, d] : st[v]) {
			auto it = st[x].lower_bound(pii(subt, 0));
			if (it != st[x].end()) fmax(ans[subt], d + it->second - dep[x] * 2);
			if (it != st[x].begin()) --it, fmax(ans[min(subt, it->first)], d + it->second - dep[x] * 2);
		}
		for (auto& [subt, d] : st[v]) add(subt, d, x);
	}
	add(num[x], dep[x], x);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N;
	int i, a, b;
	for (i = 1; i < N; i++) cin >> a >> b, adj[a].push_back(b), adj[b].push_back(a);
	dfs(1);
	calc(1);
	for (i = N; i >= 1; i--) fmax(ans[i], ans[i + 1]);
	for (i = 1; i <= N; i++) {
		if (i & 1) cout << 1 << ln;
		else cout << ans[i >> 1] + 1 << ln;
	}
}

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