Submission #1216795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216795		siewjh	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	119 ms	34064 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int sz[MAXN], d[MAXN], mxc[MAXN], ans[MAXN];
vector<int> adj[MAXN], szv[MAXN];
int nodes;
vector<int> szp;
void dfs(int x, int par, int dep){
	sz[x] = 1; d[x] = dep;
	for (int nn : adj[x]){
		if (nn == par) continue;
		dfs(nn, x, dep + 1);
		sz[x] += sz[nn]; mxc[x] = max(mxc[x], sz[nn]);
	}
}
void dfs2(int x, int par){
	for (int nn : adj[x]){
		if (nn == par) continue;
		dfs2(nn, x);
		if (szv[nn].size() > szv[x].size()) swap(szv[nn], szv[x]);
		for (int i = szv[nn].size(); i >= 1; i--){
			ans[i] = max(ans[i], szv[x][i - 1] + szv[nn][i - 1] - 2 * d[x]);
			szv[x][i - 1] = max(szv[x][i - 1], szv[nn][i - 1]);
		}
	}
	for (int i = mxc[x] + 1; i <= sz[x]; i++) szv[x].push_back(d[x]);
}
void dfs3(int x, int par){
	auto it = lower_bound(szp.begin(), szp.end(), mxc[x] + 1);
	for (int i = mxc[x] + 1; i <= sz[x]; i++){
		if (it != szp.end() && i > *it) it++;
		if (it == szp.end()) break;
		ans[i] = max(ans[i], (int)(szp.end() - it));
	}
	for (int nn : adj[x]){
		if (nn == par) continue;
		szp.push_back(nodes - sz[nn]);
		dfs3(nn, x);
		szp.pop_back();
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> nodes;
	for (int i = 1; i < nodes; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	dfs(1, -1, 0); dfs2(1, -1); dfs3(1, -1);
	for (int i = 1; i <= nodes; i++) cout << (i & 1 ? 1 : ans[i >> 1] + 1) << '\n';
}

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