Submission #595725

#	Time	Username	Problem	Language	Result	Execution time	Memory
595725		penguinhacker	Meetings 2 (JOI21_meetings2)	C++17	20 / 100	212 ms	86112 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ar array
 
const int mxN=2e5, INF=1e9;
int n, d[mxN], s[mxN], anc[mxN][18], ans[mxN+1], tin[mxN], tout[mxN];
vector<int> adj[mxN], stk;
set<ar<int, 2>> active;
 
void dfs(int u=0) {
	s[u]=1;
	tin[u]=stk.size();
	stk.push_back(d[u]);
	for (int i=1; i<18; ++i)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	for (int v : adj[u])
		if (v!=anc[u][0]) {
			d[v]=d[u]+1, anc[v][0]=u;
			dfs(v);
			s[u]+=s[v];
			stk.push_back(d[u]);
		}
	tout[u]=stk.size()-1;
}

bool ia(int u, int v) {
	return tin[u]<=tin[v]&&tout[v]<=tout[u];
}
 
int lca(int u, int v) {
	if (ia(u, v)||ia(v, u))
		return ia(u, v)?u:v;
	for (int i=17; ~i; --i)
		if (!ia(anc[u][i], v))
			u=anc[u][i];
	return anc[u][0];
}
 
int dist(int u, int v) {
	return d[u]+d[v]-2*d[lca(u, v)];
}

struct Node {
	int ans, mn, mx, lhs, rhs;
} st[1<<19];
 
Node cmb(Node a, Node b) {
	return {
		max({a.ans, b.ans, a.rhs+b.mx, a.mx+b.lhs}),
		min(a.mn, b.mn),
		max(a.mx, b.mx),
		max({a.lhs, b.lhs, -2*a.mn+b.mx}),
		max({a.rhs, b.rhs, a.mx-2*b.mn})
	};
}
 
void bld(int u=1, int l=0, int r=2*n-2) {
	if (l==r) {
		st[u].mn=stk[l];
		st[u].mx=st[u].lhs=st[u].rhs=-INF;
		return;
	}
	int mid=(l+r)/2;
	bld(2*u, l, mid);
	bld(2*u+1, mid+1, r);
	st[u]=cmb(st[2*u], st[2*u+1]);
}
 
void upd(int i, bool on, int u=1, int l=0, int r=2*n-2) {
	if (l==r) {
		//cout << "activating " << i << " " << on << endl;
		st[u].mx=on?stk[l]:-INF;
		st[u].lhs=st[u].rhs=on?-stk[l]:-INF;
		return;
	}
	int mid=(l+r)/2;
	i<=mid?upd(i, on, 2*u, l, mid):upd(i, on, 2*u+1, mid+1, r);
	st[u]=cmb(st[2*u], st[2*u+1]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs();
	assert(stk.size()==2*n-1);
	bld();

	vector<ar<int, 2>> subtrees;
	for (int i=1; i<n; ++i)
		subtrees.push_back({s[i], i});
	sort(subtrees.begin(), subtrees.end());
	fill(ans, ans+n+1, 1);
	int best=1;
	for (int i=n/2; i; --i) {
		while(subtrees.size()&&subtrees.back()[0]>=i) {
			int u=subtrees.back()[1];
			subtrees.pop_back();
			auto it=active.lower_bound({tin[u]});
			if (it!=active.begin()) {
				--it;
				int v=(*it)[1];
				if (ia(v, u)) {
					upd(tin[v], 0);
					active.erase(it);
				}
			}
			//for (ar<int, 2> x : active)
			//	best=max(best, dist(u, x[1])+1);
			upd(tin[u], 1);
			active.insert({tin[u], u});
			best=max(best, st[1].ans+1);
		}
		//cout << i << " " << best << endl;
		for (ar<int, 2> x : active) {
			int u=x[1];
			if (n-s[u]>=i) {
				int v=u;
				for (int j=17; ~j; --j)
					if (n-s[anc[v][j]]>=i)
						v=anc[v][j];
				best=max(best, d[u]-d[v]+2);
			}
		}
		ans[2*i]=best;
	}
	for (int i=1; i<=n; ++i)
		cout << ans[i] << "\n";
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from meetings2.cpp:1:
meetings2.cpp: In function 'int main()':
meetings2.cpp:94:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |  assert(stk.size()==2*n-1);
      |         ~~~~~~~~~~^~~~~~~

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