oj.uz

Submission #446630

# Submission time Handle Problem Language Result Execution time Memory
446630 2021-07-22T21:17:06 Z ritul_kr_singh Meetings 2 (JOI21_meetings2) C++17
0 / 100
 6 ms 8140 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int LIM = 2e5+2, INF = 1e9;

template<class T> struct SegmentTree{
	const T ID = -INF;
	int n, i; vector<T> a;
	SegmentTree(int N) : a((n=N)*2, ID) {}
	SegmentTree& operator[](int j){ i=j+n; return *this; }
	void operator=(T v){
		for(a[i]=v; i/=2; ) a[i] = max(a[2*i], a[2*i+1]); }
	int operator()(int l, int r){
		T x = ID;
		for(l+=n, r+=n+1; l<r; l/=2, r/=2){
			if(l & 1) x = max(x, a[l++]);
			if(r & 1) x = max(x, a[--r]);
		}
		return x;
	}
};

int n, ans[LIM], s[LIM], mxSz;
vector<int> g[LIM];
bool r[LIM], update;
SegmentTree<int> st(LIM);

void init(int u){
	s[u] = 1;
	for(int v : g[u]) if(!s[v]) init(v), s[u] += s[v];
}

int find(int u){
	for(int v : g[u]) if(!r[v] && s[v] > s[u]/2){
		s[u] -= s[v], s[v] += s[u];
		return find(v);
	}
	return u;
}

void dfs(int u, int d){
	if(update) st[s[u]] = max(st(s[u], s[u]), d);
	else ans[s[u]] = max(ans[s[u]], st(s[u], n-1) + 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){
	mxSz = 1;
	for(int v : g[u]) if(!r[v]){
		ans[s[v]+1] = max(ans[s[v]+1], st(s[v]+1, n-1));
		update = 0;
		dfs(v, 1);
		update = 1;
		dfs(v, 1);

		mxSz = max(mxSz, s[v] + 1);
	}

	for(int i=0; i<s[u]; ++i) st[i+1] = -INF;
}

void decompose(int u){
	r[u = find(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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8140 KB Output is correct
2 Correct 5 ms 8140 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Incorrect 5 ms 8124 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8140 KB Output is correct
2 Correct 5 ms 8140 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Incorrect 5 ms 8124 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8140 KB Output is correct
2 Correct 5 ms 8140 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Incorrect 5 ms 8124 KB Output isn't correct
5 Halted 0 ms 0 KB -