Submission #869296

#	Time	Username	Problem	Language	Result	Execution time	Memory
869296		NK_	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	281 ms	63824 KiB

meetings2

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 19;

struct T {
	int a, b, c, ab, bc, abc;
	T() { a = b = c = ab = bc = abc = -MOD; }
	T(int x) {
		a = x, b = -2*x, c = x;
		ab = -x, bc = -x;
		abc = 0;
	}
};

struct Seg {
	const T ID = T(); T comb(T a, T b) {
		T r = T(); 

		r.a = max(a.a, b.a), r.b = max(a.b, b.b), r.c = max(a.c, b.c);
		r.ab = max({a.ab, b.ab, a.a + b.b}), r.bc = max({a.bc, b.bc, a.b + b.c});
		r.abc = max({a.abc, b.abc, a.ab + b.c, a.a + b.bc});

		return r;
	};

	V<T> seg; int n;
	void init(int _n) {
		n = 1; while(n < _n) n *= 2;
		seg.assign(2*n, ID);
	}

	void pull(int x) { seg[x] = comb(seg[2*x], seg[2*x+1]); }

	void upd(int p, T x) {
		seg[p += n] = x; for(p /= 2; p; p /= 2) pull(p);
	}

	T get() { return seg[1]; };
};


int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; cin >> N;

	V<vi> adj(N); 
	for(int i = 0; i < N-1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	vi sub(N), dep(N), X(N, MOD); int TIME = 0;
	V<vi> pos(N);
	function<void(int, int)> prep = [&](int u, int p) {
		sub[u] = 1; dep[u] = (p == -1 ? 0 : dep[p] + 1); pos[u].pb(TIME++);
		for(auto& v : adj[u]) if (v != p) {
			prep(v, u);
			X[u] = min(X[u], N - sub[v]);
			sub[u] += sub[v];
			pos[u].pb(TIME++);
		}

		X[u] = min(X[u], sub[u]);
	};

	prep(0, -1);

	vi U(N); iota(begin(U), end(U), 0);
	sort(begin(U), end(U), [&](int a, int b) {
		return X[a] > X[b];
	});	

	vi ans(N, 1); 
	Seg st; st.init(TIME);
	for(int i = N / 2, cur = 0; i >= 1; i--) {
		while(cur < N && X[U[cur]] >= i) {
			int x = U[cur];
			for(auto t : pos[x]) {
				st.upd(t, T(dep[x]));
			}
			cur++;
		}
		ans[2 * i - 1] = st.get().abc + 1;
	}	

	for(int i = 0; i < N; i++) cout << ans[i] << nl;


	exit(0-0);
} 	 

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