Submission #1076138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076138		0npata	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	403 ms	55908 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define vec vector

const int MXN = 4e5+10;

vec<int> tree[MXN];
int sz[MXN];
vec<pair<int, int>> sz_bst[MXN];
vec<int> ans(MXN, 1);
bool iscentr[MXN];

void compszs(int u, int p = -1) {
	sz[u] = 0;
	if(iscentr[u]) return;
	sz[u] = 1;
	for(int v : tree[u]) {
		if(v == p) continue;
		compszs(v, u);
		sz[u] += sz[v];
	}
}

int findcentr(int u, int mxsz, int p = -1) {
	for(int v : tree[u]) {
		if(v == p) continue;
		if(sz[v] > mxsz) return findcentr(v, mxsz, u);
	}
	return u;
}

vec<pair<int, int>> upd(vec<pair<int, int>> bst, pair<int, int> val) {
	if(bst.size() == 0) return {val};
	if(val.second > bst[0].second) {
		if(val.first == bst[0].first) {
			bst[0] = val;
		}
		else {
			if(bst.size() > 1) {
				bst[1] = bst[0];
			}
			else {
				bst.push_back(bst[0]);
			}
			bst[0] = val;
		}
	}
	else if(bst.size() == 1) {
		if(bst[0].first != val.first) {
			bst.push_back(val);
		}
	}
	else {
		assert(bst.size() == 2);
		if(val.second > bst[1].second && val.first != bst[0].first) {
			bst[1] = val;
		}
	}
	return bst;
}

void compbsts(int u, int p, int sa, int d) {
	sz[u] = 0;
	if(iscentr[u]) return;
	sz[u] = 1;
	for(int v : tree[u]) {
		if(v == p) continue;
		compbsts(v, u, sa, d+1);
		sz[u] += sz[v];
	}
	sz_bst[sz[u]] = upd(sz_bst[sz[u]], {sa, d});
}

void divandconq(int u) {
	compszs(u);
	int v = findcentr(u, sz[u]/2);
	for(int i = 0; i<=sz[u]; i++) {
		sz_bst[i] = {};
	}
	sz[v] = 0;
	for(int w : tree[v]) {
		compbsts(w, v, w, 1);
		sz[v] += sz[w];
	}
	iscentr[v] = true;
	int mxd = 0;
	for(int i = sz[v]; i>=0; i--) {
		if(sz_bst[i].size() > 0) {
			mxd = max(sz_bst[i][0].second, mxd);
		}
		//cerr << mxd << ' ';
		ans[i*2] = max(ans[i*2], mxd+1);
	}
	//cerr << '\n';
	vec<pair<int, int>> bst{};
	for(int i = sz[v]; i>=0; i--) {
		for(auto sb : sz_bst[i]) {
			bst = upd(bst, sb);
		}
		if(bst.size() > 1) {
			ans[i*2] = max(ans[i*2], bst[0].second+bst[1].second+1);
		}
	}
	for(int w : tree[v]) {
		if(iscentr[w]) continue;
		divandconq(w);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N;
	cin >> N;
	for(int i = 0; i<N-1; i++) {
		int U, V;
		cin >> U >> V;
		tree[U].push_back(V);
		tree[V].push_back(U);
	}
	divandconq(1);

	for(int i = 1; i<=N; i++) {
		cout << ans[i] << '\n';
	}
}

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