Submission #446641

#	Time	Username	Problem	Language	Result	Execution time	Memory
446641		ritul_kr_singh	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	1223 ms	20832 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
#define sp << ' ' <<
#define nl << '\n'
 
const int LIM = 2e5+2, INF = 1e9;

struct FenwickTree{
	vector<int> a; int n, s;
	FenwickTree(int N) : a((n=N)+1, -INF) {}
	void update(int i, int v){
		i = n - i;
		for(; i<=n; i+=i&-i) a[i] = max(a[i], v);
	}
	int operator()(int i){
		i = n - i, s = -INF;
		for(; i>=1; i-=i&-i) s = max(s, a[i]);
		return s;
	}
};
 
int n, ans[LIM], s[LIM], mxSz;
vector<int> g[LIM];
bool r[LIM], update;
FenwickTree f(0);
 
void init(int u){
	s[u] = 1;
	for(int v : g[u]) if(!s[v]) init(v), s[u] += s[v];
}

void find(int &u){
	for(int q=1; q; ){
		q = 0;
		for(int v : g[u]) if(!r[v] && s[v] > s[u]/2){
			s[u] -= s[v], s[v] += s[u], u = v, q = 1;
			break;
		}
	}
}
 
void dfs(int u, int d){
	if(update) f.update(s[u], d);
	else ans[s[u]] = max(ans[s[u]], f(s[u]) + d);
	if(s[u] <= mxSz) ans[s[u]] = max(ans[s[u]], d);
 
	for(int v : g[u]) if(!r[v] && s[v] < s[u]) dfs(v, d+1);
}
 
void calc(int u){
	f = FenwickTree(s[u] + 1);

	for(int v : g[u]) if(!r[v]){
		ans[s[v]+1] = max(ans[s[v]+1], f(s[v]+1));
 		mxSz = s[u] - s[v];
		update = 0, dfs(v, 1);
		update = 1, dfs(v, 1);
	}
}
 
void decompose(int u){
	find(u), r[u] = 1;
	calc(u);
	reverse(g[u].begin(), g[u].end());
	calc(u);
 
	for(int v : g[u]) if(!r[v]) decompose(v);
}
 
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=1; i<n; ++i){
		int u, v; cin >> u >> v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
 
	init(0);
	decompose(0);
 
	for(int i=n; --i; ) ans[i] = max(ans[i], ans[i+1]);
	for(int i=1; i<=n; ++i){
		if(i & 1) cout << 1 nl;
		else cout << ans[i/2]+1 nl;
	}
}

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