Submission #386975

#	Time	Username	Problem	Language	Result	Execution time	Memory
386975		ogibogi2004	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	2669 ms	25716 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
vector<int>g[MAXN];
bool used[MAXN];
int ans[MAXN];
int n;
int subtree[MAXN];
int max1=1;
int dfs(int u,int p)
{
	int val=1;
	for(auto xd:g[u])
	{
		if(xd==p)continue;
		int t=dfs(xd,u);
		max1=max(max1,2*min(t,n-t));
		val+=t;
	}
	return val;
}
void dfs1(int u,int p)
{
	subtree[u]=1;
	for(auto xd:g[u])
	{
		if(xd==p)continue;
		if(used[xd])continue;
		dfs1(xd,u);
		subtree[u]+=subtree[xd];
	}
}
int find_centroid(int u,int p,int n1)
{
	for(auto xd:g[u])
	{
		if(xd==p)continue;
		if(used[xd])continue;
		if(subtree[xd]>n1/2)
		{
			return find_centroid(xd,u,n1);
		}
	}
	return u;
}
struct BIT
{
	int fen[2*MAXN];
	void update(int idx,int val)
	{
		idx++;
		for(;idx<2*MAXN;idx+=idx&(-idx))
		{
			fen[idx]=max(fen[idx],val);
		}
	}
	void wipe(int idx)
	{
		idx++;
		for(;idx<2*MAXN;idx+=idx&(-idx))
		{
			fen[idx]=0;
		}
	}
	int query(int idx)
	{
		idx++;
		int ret=0;
		for(;idx>0;idx-=idx&(-idx))
		{
			ret=max(ret,fen[idx]);
		}
		return ret;
	}
}fen;
void dfs_query(int u,int p,int l)
{
	int t=subtree[u];
	//cout<<"query "<<u<<" "<<t<<" "<<l<<endl;
	//cout<<l+fen.query(MAXN-t)+1<<endl;
	ans[2*t]=max(ans[2*t],l+fen.query(MAXN-t)+1);
	for(auto xd:g[u])
	{
		if(xd==p)continue;
		if(used[xd])continue;
		dfs_query(xd,u,l+1);
	}
}
void dfs_update(int u,int p,int l)
{
	int t=subtree[u];
	fen.update(MAXN-t,l);
	//cout<<"update "<<u<<" "<<t<<" "<<l<<endl;
	for(auto xd:g[u])
	{
		if(xd==p)continue;
		if(used[xd])continue;
		dfs_update(xd,u,l+1);
	}
}
void dfs_wipe(int u,int p)
{
	int t=subtree[u];
	fen.wipe(MAXN-t);
	for(auto xd:g[u])
	{
		if(xd==p)continue;
		if(used[xd])continue;
		dfs_wipe(xd,u);
	}
}
void decompose(int u)
{
	dfs1(u,0);
	int c=find_centroid(u,0,subtree[u]);
	//cout<<"  "<<c<<endl;
	dfs1(c,0);
	used[c]=1;
	for(auto xd:g[c])
	{
		if(used[xd])continue;
		dfs_query(xd,c,1);
		dfs_update(xd,c,1);
	}
	for(auto xd:g[c])
	{
		if(used[xd])continue;
		dfs_wipe(xd,c);
	}
	//cout<<"-------------\n";
	reverse(g[c].begin(),g[c].end());
	for(auto xd:g[c])
	{
		if(used[xd])continue;
		dfs_query(xd,c,1);
		dfs_update(xd,c,1);
	}
	for(auto xd:g[c])
	{
		if(used[xd])continue;
		dfs_wipe(xd,c);
	}
	for(auto xd:g[c])
	{
		if(used[xd]==0)
		{
			decompose(xd);
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
	{
		ans[i]=1;
	}
	dfs(1,0);
	for(int i=2;i<=max1;i+=2)
	{
		ans[i]=2;
	}
	decompose(1);
	for(int i=n;i>=3;i--)
	{
		ans[i-2]=max(ans[i-2],ans[i]);
	}
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<endl;
	}
return 0;
}

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