Submission #457389

#	Time	Username	Problem	Language	Result	Execution time	Memory
457389		8e7	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	501 ms	41644 KiB

meetings2

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn];
int siz[maxn], dep[maxn], anc[18][maxn];
void dfs(int n, int par, int d) {
	anc[0][n] = par;
	dep[n] = d;
	siz[n] = 1;
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, d + 1);
			siz[n] += siz[v];
		}
	}
}
int tot;
int get_centroid(int n, int par){
	for (int v:adj[n]) {
		if (v != par && 2 * siz[v] >= tot) {
			return get_centroid(v, n);	
		}
	}
	return n;
}
int dist(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	int oa = a, ob = b;
	int hdif = dep[a] - dep[b], cnt = 0;
	while (hdif) {
		if (hdif & 1) a = anc[cnt][a];
		hdif >>= 1, cnt++;
	}
	if (a == b) return dep[oa] - dep[ob] + 1;
	for (int i = 17;i >= 0;i--) {
		if (anc[i][a] != anc[i][b]) {
			a = anc[i][a], b = anc[i][b];
		}
	}
	return dep[oa] + dep[ob] - 2 * dep[anc[0][a]] + 1;
}
vector<pii> a;
int ans[maxn];
int main() {
	io
	int n;
	cin >> n;
	tot = n;
	for (int i = 0;i < n - 1;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0, 0);
	int root = get_centroid(1, 0);	
	//debug(root);
	dfs(root, 0, 0);
	for (int i = 1;i <= n;i++) {
		a.push_back({siz[i], i});
	}
	sort(a.begin(), a.end(), [&](pii x, pii y){return x.ff > y.ff;});
	for (int i = 1;i < 18;i++) {
		for (int j = 1;j <= n;j++) anc[i][j] = anc[i - 1][anc[i - 1][j]];
	}
	int p1 = root, p2 = root, ind = 0;
	for (int i = n / 2;i > 0;i--) {
		while (ind < n && a[ind].ff >= i) {
			int p = a[ind].ss;
			//debug(p, dist(p, p1), dist(p1, p2));
			if (dist(p, p1) > dist(p2, p1)) p2 = p;
			if (dist(p, p2) > dist(p1, p2)) p1 = p;
			ind++;
		}
		//debug(p1, p2);
		ans[i * 2] = dist(p1, p2);
	}	
	for (int i = 1;i <= n;i++) {
		if (i % 2) cout << 1 << "\n";
		else cout << ans[i] << "\n";
	}
}
/*
5
1 2
2 3
4 2
3 5
*/

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