Submission #1237794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237794		ebrambill	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	371 ms	24232 KiB

meetings2

//In the name of GOD

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

#define pb push_back

const int maxN=2e5+5;
int n, sz[maxN], cent, a[maxN], b[maxN], ans[maxN], curn, droot[maxN];
bool mark[maxN]={true};
vector<int> neib[maxN];

void fcent(int v, int p=-1){
	sz[v]=1;
	for (int u: neib[v]){
		if(u!=p and !mark[u]){
		   	fcent(u, v);
			sz[v]+=sz[u];
		}
	}
	if (curn-sz[v]<=curn/2 and sz[v]<(mark[cent] ? n+1 : sz[cent]))
		cent=v;
}
void solz(int v, int p=-1){
	sz[v]=1;
	for (int u: neib[v]){
		if(u!=p and !mark[u]){
			droot[u]=droot[v]+1;
			solz(u, v);
			sz[v]+=sz[u];
		}
	}
}

void dfs(int v, int p=-1){
	for (int u: neib[v]){
		if(u!=p and !mark[u]){
			if(v==cent) fill(b, b+sz[u]+2, 0);
			dfs(u, v);
			if(v==cent) {
				for (int i=sz[u]; i>=0; i--){
					b[i]=max(b[i], b[i+1]);
					ans[i]=max(ans[i], b[i]+a[i]);
					a[i]=max(a[i], b[i]);
				}
			}
		}
	}
	if(v!=cent) b[sz[v]]=max(b[sz[v]], droot[v]);
}

void solve(int x){
	if(curn==1) return;
	fill(a, a+curn+1, 0);
	fcent(x);
	droot[cent]=0;
	solz(cent);
	dfs(cent);
	mark[cent]=true;
	vector<int> nxt;
	for (int u: neib[cent])
	   if(!mark[u]) nxt.pb(u);
	for (int u: nxt){
		curn=sz[u];
		solve(u);
	}
}

int main(){
	cin >>n;
	for (int i=1, u, v; i<n; i++){
		cin >>u >>v;
		neib[u].pb(v);
		neib[v].pb(u);
	}

	curn=n;
	solve(1);

	for (int i=1; i<=n; i++)
		cout <<(i%2 ? 1 : ans[i/2]+1) <<'\n';
}

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