Submission #1014739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014739		NintsiChkhaidze	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	505 ms	42836 KiB

meetings2

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define ll long long
using namespace std;

const int N = 2e5 + 5;
vector <int> v[N];
int c = -1,ans[N],sz[N],dep[N],d[25][N];
pii arr[N];

int findcentroid(int x,int par,int n){
	int s = 1;
	for (int to: v[x]){
		if (to == par) continue;
		s += findcentroid(to,x,n);
	}

	if (c == -1 && (par == -1 || s * 2 >= n)) c = x;
	return s;
}

int lca(int x,int y){
	if (dep[x] < dep[y]) swap(x,y);
	for (int i = 20; i >= 0; i--)
		if (dep[d[i][x]] >= dep[y]) x = d[i][x];
	if (x == y) return x;
 
	for (int i = 20; i >= 0; i--)
		if (d[i][x] != d[i][y]) x = d[i][x],y = d[i][y];
 
	return d[0][x];
}

void dfs(int x,int par){
	sz[x] = 1;
	d[0][x] = par;
	dep[x] = dep[par] + 1;
	for (int to: v[x]){
		if (to == par) continue;
		dfs(to,x);
		sz[x] += sz[to];
	}
}

int getdistance(int x,int y){
	int c=lca(x,y);
	return dep[x]+dep[y]-2*dep[c]+1;
}

signed main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n;
	cin>>n;

	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}

	findcentroid(1,-1,n);
	dfs(c,c);
	for (int j = 1; j <= 20 ; j++)
		for (int i = 1; i <= n; i++)
			d[j][i] = d[j - 1][d[j - 1][i]];

	for (int i = 1; i <= n; i++)
		arr[i] = {sz[i],i};
	sort(arr+1,arr+n+1);

	int d1 = 0,d2 = 0,D=0,mx = 0;

	for (int i = n; i >= 1; i--){
		int x = arr[i].s;
		if (!d1) d1=d2=x,D=1;
		else{
			if (getdistance(d1,x) > D) {
				d2 = x;
				D = getdistance(d1,x);
			}

			if (getdistance(d2,x) > D){
				d1 = x;
				D = getdistance(d2,x);
			}
		}
		
		mx=max(mx,D);
		ans[arr[i].f] = mx;
	}

	for (int i = n; i >= 1; i--){
		ans[i] = max(ans[i],ans[i + 1]);
	}

	for (int i = 1; i <= n; i++){
		if (i&1) cout<<1<<endl;
		else cout<<ans[i/2]<<endl;
	}
}

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