Submission #419475

#	Time	Username	Problem	Language	Result	Execution time	Memory
419475		amoo_safar	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	536 ms	49220 KiB

meetings2

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second

using namespace std;

const int N = 2e5 + 10;
const int Log = 20;

vector<int> G[N];
vector< pair<int, int> > E[N];

int n;
int sp[N][Log];
int sub[N], dep[N];

int DFS(int u, int p, int d){
	sp[u][0] = p;
	sub[u] = 1;
	dep[u] = d;
	for(int l = 1; l < Log; l++)
		sp[u][l] = sp[ sp[u][l - 1] ][l - 1];
	for(auto adj : G[u])
		if(adj != p)
			sub[u] += DFS(adj, u, d + 1);
	E[min(n - sub[u], sub[u])].pb({u, p});
	return sub[u];
}

int LCA(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	for(int i = 0; i < Log; i++)
		if((dep[u] - dep[v]) >> i & 1)
			u = sp[u][i];
	if(u == v) return u;
	for(int l = Log - 1; l >= 0; l--)
		if(sp[u][l] != sp[v][l])
			u = sp[u][l], v = sp[v][l];
	return sp[u][0];
}
int dist(int u, int v){ return dep[u] + dep[v] - 2 * dep[LCA(u, v)]; }

int ans[N];
int mk[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	int u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	DFS(1, 0, 0);
	
	u = -1, v = -1;
	for(int i = n; i >= 1; i--){
		if(i & 1){
			ans[i] = 1;
			continue;
		}
		for(auto [fr, to] : E[i / 2]){
			if(u == -1) u = fr, v = to, mk[fr] = 1, mk[to] = 1;

			if(!mk[fr]){
				if(dist(u, v) < dist(u, fr))
					v = fr;
				if(dist(u, v) < dist(v, fr))
					u = fr;
				mk[fr] = 1;
			}
			if(!mk[to]){
				if(dist(u, v) < dist(u, to))
					v = to;
				if(dist(u, v) < dist(v, to))
					u = to;
				mk[to] = 1;
			}
		}
		ans[i] = u == -1 ? 1 : dist(u, v) + 1;
	}
	for(int i = 1; i <= n; i++)
		cout << ans[i] << '\n';
	return 0;
}

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