Submission #1099519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099519		vjudge1	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	570 ms	24656 KiB

meetings2

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define fi first
#define se second
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fu(x,a,b) for (auto x=a;x<=b;x++)
#define fd(x,a,b) for (auto x=a;x>=b;x--)
#define int ll

using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

typedef pair<int, int> ii;
const int N = 2e5+5;
const int mod = 998277353;
const int inf = 1e18;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 

int n;
vector<int> adj[N];
int sz[N], ans[N], dist[N], mx[N], lst[N];
bool check[N];

void predfs(int u,int p) 
{
	sz[u] = 1;
	for (auto v : adj[u]) 
	{
		if (v==p || check[v]) continue;
		predfs(v,u);
		sz[u] += sz[v];
	}
}

int centroid(int u, int p, int n) 
{
	for (auto v : adj[u]) 
	{
		if (check[v] || v==p) continue;
		if (sz[v] > n/2) return centroid(v,u,n);
	}
	return u;
}

void dfs1(int u,int p)
{
	dist[u] = dist[p]+1;
	for (auto v : adj[u])
	{
		if (v==p || check[v]) continue;
		dfs1(v,u);
	}
	mx[sz[u]] = max(mx[sz[u]],dist[u]);
}

void dfs(int u) 
{
	predfs(u,0);
	int ct = centroid(u,0,sz[u]);
	predfs(ct,0);
	dist[ct] = 1;
	int tot = 0;
	//cout<<ct<<endl;
	for (auto v : adj[ct]) 
	{
		if (check[v]) continue;
		dfs1(v,ct);
		//cout<<v<<endl;
		tot = max(tot,sz[v]);     
		for (int i=sz[v]-1;i>=0;i--) mx[i] = max(mx[i],mx[i+1]);
		// for (int i=0;i<=sz[v];i++) cout<<mx[i]<<" ";
		// cout<<endl;
		for (int i=sz[v];i>=0;i--) 
		{
			ans[i*2] = max(ans[i*2], mx[i] + max(lst[i],1ll) - 1);
			lst[i] = max(lst[i],mx[i]), mx[i] = 0;
		}
	}
	//cout<<endl;
	for (int i=0;i<=tot;i++) mx[i] = lst[i] = 0;
	check[ct] = true;
	for (auto v : adj[ct]) 
	{
		if (check[v]) continue;
		dfs(v);
	}
}

void solve()
{
	cin>>n;
	for (int i=1;i<n;i++) 
	{
		int u,v,w; cin>>u>>v;
		adj[u].pb(v); adj[v].pb(u);
	}
	dfs(1);
	for (int i=1;i<=n;i++) cout<<(ans[i] ? ans[i] : 1)<<endl;
}

signed main()
{
	bruh
	//freopen("input.inp","r",stdin);
	//freopen("output.inp","w",stdout);
	int t = 1;
	//cin>>t;
	while (t--)
	{
		solve();
		cout<<"\n";
	}
}

Compilation message (stderr)

meetings2.cpp: In function 'void solve()':
meetings2.cpp:102:11: warning: unused variable 'w' [-Wunused-variable]
  102 |   int u,v,w; cin>>u>>v;
      |           ^

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