Submission #1237765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237765		ebrambill	Meetings 2 (JOI21_meetings2)	C++17	4 / 100	2 ms	584 KiB

meetings2

//In the name of GOD

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

#define pb push_back

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

void fcent(long long v, long long p=-1){
	sz[v]=1;
	for (long long 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(long long v, long long p=-1){
	sz[v]=1;
	for (long long u: neib[v]){
		if(u!=p and !mark[u]){
			droot[u]=droot[v]+1;
			solz(u, v);
			sz[v]+=sz[u];
		}
	}
}

void dfs(long long v, long long p=-1){
	for (long long 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 (long long 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(long long x){
	if(curn==1) return;
	fill(a, a+curn+1, 0);
	fcent(x);
	droot[cent]=0;
	solz(cent);
	dfs(cent);
	mark[cent]=true;
	vector<long long> nxt;
	for (long long u: neib[cent])
	   if(!mark[u]) nxt.pb(u);
	for (long long u: nxt){
		curn=sz[u];
		solve(u);
	}
}

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

	curn=n;
	solve(1);

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

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