Submission #630605

#	Time	Username	Problem	Language	Result	Execution time	Memory
630605		valerikk	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	866 ms	33420 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define all(a) begin(a), end(a)
#define sz(a) ((int) (a).size())

using ll = long long;

const int N = 200005;

int n;
vector<int> g[N];
int init_sz[N], init_d[N];
bool used[N];
int sz[N], d[N];
int ans[N], first[N];

void upd_ans(int x, int y) {
	ans[2 * x] = max(ans[2 * x], y);
}

void dfs_prepare(int u = 0, int p = -1, int cd = 0) {
	init_sz[u] = 1;
	init_d[u] = cd;
	for (int v : g[u]) {
		if (v != p) {
			dfs_prepare(v, u, cd + 1);
			init_sz[u] += init_sz[v];
		}
	}
}	

int get_subtree_sz(int u, int v) {
	return init_d[u] < init_d[v] ? init_sz[v] : n - init_sz[u];
}

void dfs(int u, int p = -1, int cd = 0) {
	sz[u] = 1;
	d[u] = cd;
	for (int v : g[u]) {
		if (!used[v] && v != p) {
			dfs(v, u, cd + 1);
			sz[u] += sz[v];
		}
	}
}

int centr(int all_sz, int u, int p = -1) {
	for (int v : g[u]) {
		if (!used[v] && v != p && 2 * sz[v] > all_sz) {
			return centr(all_sz, v, u);
		}
	}
	return u;
}

void dfs_ans(int root, vector<pair<int, int>> &vs, int u, int p = -1) {
	if (u != root) {
		first[u] = p == root ? u : first[p];
		vs.push_back({get_subtree_sz(p, u), u});
		upd_ans(min(get_subtree_sz(p, u), get_subtree_sz(first[u], root)), d[u] + 1);
	}
	for (int v : g[u]) {
		if (!used[v] && v != p) {
			dfs_ans(root, vs, v, u);
		} 
	}
}

void solve(int root) {
	dfs(root);
	vector<pair<int, int>> vs;
	dfs_ans(root, vs, root);
	sort(all(vs));
	reverse(all(vs));
	vector<pair<int, int>> cur;
	for (auto [s, v] : vs) {
		for (auto [du, fu] : cur) {
			if (fu != first[v]) {
				upd_ans(s, du + d[v] + 1);
			}
		}	
		cur.push_back({d[v], first[v]});
		sort(all(cur));
		bool cont = true;
		for (int i = 0; i < sz(cur) && cont; ++i) {
			for (int j = i + 1; j < sz(cur) && cont; ++j) {
				if (cur[i].y == cur[j].y) {
					cur.erase(begin(cur) + i);
					cont = false;
				}
			}
		}
		if (sz(cur) == 3) {
			cur.erase(begin(cur));
		}
	}
	used[root] = true;
	for (int v : g[root]) {
		if (!used[v]) {
			solve(centr(sz[v], v));
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		g[a].push_back(b);
		g[b].push_back(a);
	}	
	for (int i = 1; i <= n; ++i) {
		ans[i] = 1;
	}
	dfs_prepare();
	dfs(0);
	solve(centr(n, 0));
	for (int i = n; i >= 2; --i) {
		ans[i - 2] = max(ans[i - 2], ans[i]);
	}
	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << "\n";
	}
	return 0;
}

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