Submission #523296

#	Time	Username	Problem	Language	Result	Execution time	Memory
523296		amunduzbaev	Meetings 2 (JOI21_meetings2)	C++17	20 / 100	4057 ms	136236 KiB

meetings2

#include "bits/stdc++.h"
using namespace std;
 
#define ar array

const int N = 2e5 + 5;
vector<int> edges[N], tt;
int sub[N], n, C, d[N];
int used[N], ss[N], rr[N];

void dff(int u, int p = -1){
	ss[u] = 1;
	for(auto x : edges[u]){
		if(x == p) continue;
		dff(x, u);
		ss[u] += ss[x];
	}
}

void dfs(int u, int n, int p = -1){
	sub[u] = 1;
	if(p == -1) d[u] = 0;
	for(auto x : edges[u]){
		if(x == p) continue;
		if(!used[x]){
			d[x] = d[u] + 1;
			dfs(x, n, u);
			sub[u] += sub[x];
		} else {
			if(ss[u] > ss[x]) sub[u] += ss[x];
			else sub[u] += (::n - ss[u]);
		}
	}
	if(sub[u] > n / 2 && C == -1) C = u;
}

void get(int u, int p = -1){
	tt.push_back(u);
	for(auto x : edges[u]){
		if(used[x] || x == p) continue;
		get(x, u);
	}
}

void dec(int u, int n){
	C = -1;
	dfs(u, n), dfs(C, n);
	//~ cout<<C<<endl;
	
	set<ar<int, 2>> ss;
	
	auto add = [&](ar<int, 2> x){
		auto it = ss.lower_bound({x[0] + 1, -1});
		if(it != ss.end()){
			if((*it)[1] >= x[1]) return;;
		}
		
		vector<ar<int, 2>> del;
		while(it != ss.begin()){
			it--;
			if((*it)[1] <= x[1]) del.push_back(*it);
			else break;
		}
		
		for(auto v : del) ss.erase(v);
		ss.insert(x);
	};
	
	for(auto x : edges[C]){
		if(used[x]) continue;
		tt.clear(); get(x, C);
		for(auto x : tt){
			auto it = ss.lower_bound({sub[x], -1});
			if(it != ss.end()){
				rr[sub[x]] = max(rr[sub[x]], d[x] + (*it)[1] + 1);
			}
		} for(auto x : tt) add({sub[x], d[x]});
	}
	
	reverse(edges[C].begin(), edges[C].end());
	ss.clear();
	for(auto x : edges[C]){
		if(used[x]) continue;
		tt.clear(); get(x, C);
		for(auto x : tt){
			auto it = ss.lower_bound({sub[x], -1});
			if(it != ss.end()){
				rr[sub[x]] = max(rr[sub[x]], d[x] + (*it)[1] + 1);
			}
			
			rr[min(sub[x], n - (int)tt.size())] = 
			max(rr[min(sub[x], n - (int)tt.size())], d[x] + 1);
		} for(auto x : tt) add({sub[x], d[x]});
	}
	
	used[C] = 1;
	for(auto x : edges[C]){
		if(used[x]) continue;
		tt.clear(); get(x, C);
		dec(x, (int)tt.size());
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin>>n;
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	dff(1);
	dec(1, n);
	rr[n] = 1;
	for(int i=n;i>0;i--) rr[i] = max(rr[i], rr[i+1]);
	for(int i=1;i<=n;i++){
		if(i&1) cout<<1<<"\n";
		else cout<<rr[i/2]<<"\n";
	}
}

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