Submission #394214

#	Time	Username	Problem	Language	Result	Execution time	Memory
394214		oolimry	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	840 ms	31060 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

int n; 
int ans[200005];
vector<int> adj[200005];
bool cented[200005];
int sz[200005];
int dis[200005];
vector<int> nodes;

void dfs(int u, int p){
	nodes.push_back(u);
	sz[u] = 1;
	for(int v : adj[u]){
		if(cented[v] or v == p) continue;
		dis[v] = dis[u]+1;
		dfs(v, u);
		sz[u] += sz[v];
	}
}
void init(int u, int p = -1){
	dis[u] = 0;
	nodes.clear();
	dfs(u,p);
}


struct thing{ int sub, dis, sz; };

void recurse(int R){
	init(R, -1);
	
	int cent = -1;
	for(int u : nodes){
		int maxsz = sz[R] - sz[u];
		for(int v : adj[u]){
			if(cented[v] or sz[v] > sz[u]) continue;
			maxsz = max(maxsz, sz[v]);
		}
		if(maxsz <= sz(nodes)/2){
			cent = u;
			break;
		}
	}
	
	vector<thing> stuff;
	
	for(int v : adj[cent]){
		if(cented[v]) continue;
		init(v, cent);
		for(int x : nodes){
			stuff.push_back({v, dis[x], sz[x]});
		}
	}
	
	sort(all(stuff), [&](thing &a, thing &b){ return a.sz > b.sz; });
	
	ii b1 = {-1, -1}, b2 = {-2, -2};
	for(thing &s : stuff){
		///if root is the endpoint
		int SZ = 2*min(s.sz, n-s.sz);
		ans[SZ] = max(ans[SZ], s.dis+2);
		//show2(s.sub, s.dis);
		
		///if root is not endpoint		
		ii cur = ii(s.dis, s.sub);
		if(b1.second == cur.second) b1 = max(b1, cur);
		else b2 = max(b2, cur);
		if(b1 < b2) swap(b1, b2);
		
		assert(b1.second != b2.second);
		
		ans[2*s.sz] = max((lint) ans[2*s.sz], b1.first + b2.first + 3);
	}
	
	cented[cent] = true;
	for(int v : adj[cent]){
		if(cented[v]) continue;
		recurse(v);
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n;
	for(int i = 1;i < n;i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	fill(ans, ans+n+1, 1);
	
	recurse(1);
	
	int nn = n;
	if(nn&1) nn--;
	for(int i = nn;i >= 2;i -= 2) ans[i] = max(ans[i], ans[i+2]);
	for(int i = 1;i <= n;i++) cout << ans[i] << "\n";
}

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