oj.uz

Submission #595707

# Submission time Handle Problem Language Result Execution time Memory
595707 2022-07-14T02:03:04 Z penguinhacker Meetings 2 (JOI21_meetings2) C++17
0 / 100
 4 ms 5032 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5;
int n, d[mxN], s[mxN], anc[mxN][18], ans[mxN+1];
vector<int> adj[mxN];

void dfs(int u=0) {
	s[u]=1;
	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];
		}
	}
}

int lca(int u, int v) {
	if (d[u]>d[v])
		swap(u, v);
	for (int i=17; ~i; --i)
		if (d[v]-(1<<i)>=d[u])
			v=anc[v][i];
	if (u==v)
		return u;
	for (int i=17; ~i; --i)
		if (anc[u][i]!=anc[v][i])
			u=anc[u][i], v=anc[v][i];
	return anc[u][0];
}

int dist(int u, int v) {
	return d[u]+d[v]-2*d[lca(u, v)];
}

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();
	vector<ar<int, 2>> upd;
	for (int i=1; i<n; ++i)
		upd.push_back({s[i], i});
	sort(upd.begin(), upd.end());
	fill(ans, ans+n+1, 1);
	int a=-1, b=-1, dab=0;
	auto Ck=[&](int u, int v) {
		int duv=dist(u, v);
		if (a==-1||duv>dab)
			a=u, b=v, dab=duv;
	};
	for (int i=n/2; i; --i) {
		while(upd.size()&&upd.back()[0]>=i) {
			int u=upd.back()[1];
			//cout << i << " " << u << endl;
			upd.pop_back();
			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];
				//cout << u << " " << v << endl;
				Ck(u, anc[v][0]);
			}
			if (a!=-1) {
				int la=a, lb=b;
				Ck(la, u);
				Ck(lb, u);
			}
		}
		//cout << a << " " << b << " " << dab << endl;
		ans[2*i]=dab+1;
	}
	for (int i=1; i<=n; ++i)
		cout << ans[i] << "\n";
	return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 80.0

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