Submission #386296

#	Time	Username	Problem	Language	Result	Execution time	Memory
386296		kshitij_sodani	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	1566 ms	84324 KiB

meetings2

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

llo n;
llo aa,bb;
vector<llo> adj[2000001];

llo cur=-1;
llo ma[200001];
llo ne[200001];
llo ss[200001];
llo cot=0;
llo pre[200001];
llo vis[200001];
llo lev[200001];
vector<pair<llo,llo>> tt;
void dfs2(llo no,llo par2=-1,llo cot2=-1,llo levv=0){
	ss[no]=1;
	ne[no]=cot2;
	lev[no]=levv;
	for(auto j:adj[no]){
		if(vis[j]){
			continue;
		}
		if(j!=par2){
			if(par2==-1){
				cot2=j;
			}
			dfs2(j,no,cot2,levv+1);
			ss[no]+=ss[j];
		}
	}
	if(par2!=-1){
		tt.pb({ss[no],no});
	}	
}
llo pp;
llo find(llo no,llo par2=-1){
	for(auto j:adj[no]){
		if(vis[j]){
			continue;
		}
		if(ss[j]>(pp/2) and j!=par2){
			return find(j,no);
		}
	}

	return no;
}

void dec(llo no){

	dfs2(no,-1,no);
	pp=ss[no];
	no=find(no);
	tt.clear();
	dfs2(no);
	sort(tt.begin(),tt.end());

	reverse(tt.begin(),tt.end());
	//ma[no]=0;
	set<pair<llo,llo>> xx;
	//xx.insert({0,no});
	for(auto j:adj[no]){
		if(vis[j]==0){
			ma[j]=0;
			xx.insert({0,j});
		}
	}

	for(auto j:tt){
		xx.erase({-ma[ne[j.b]],ne[j.b]});
		ma[ne[j.b]]=max(ma[ne[j.b]],lev[j.b]);
		if(xx.size()){
			pair<llo,llo> cc=*(xx.begin());
			/*if(j.a==1){
				cout<<no<<":"<
			}*/
			pre[j.a]=max(pre[j.a],lev[j.b]-cc.a+1);
		}
		llo yy=n-ss[ne[j.b]];
		yy=min(yy,j.a);
		pre[yy]=max(pre[yy],lev[j.b]+1);
		xx.insert({-ma[ne[j.b]],ne[j.b]});
	}

	vis[no]=1;
	for(auto j:adj[no]){
		if(vis[j]==0){
			//cout<<no<<":"<<j<<endl;
			dec(j);

		}
	}
}
/*void dfs3(llo no,llo par2=-1,llo lev=0){
	if(par2!=-1){
		pre[min(ss[no],n-ss[ne[no]])]=max(pre[min(ss[no],n-ss[ne[no]])],lev+1);
	}
	for(auto j:adj[no]){
		if(j!=par2){
			dfs3(j,no,lev+1);
		}
	}
}*/
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;

	for(llo i=0;i<n-1;i++){
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
	}
	dec(0);
	/*for(llo i=0;i<n;i++){
		dfs2(i);
		dfs3(i);
	}*/
	for(llo j=n-1;j>=0;j--){
		pre[j]=max(pre[j+1],pre[j]);
	}
/*	for(llo j=1;j<=n;j++){
		cout<<pre[j]<<",";
	}
	cout<<endl;*/
	for(llo j=1;j<=n;j++){
		if(j%2==1){
			cout<<1<<endl;
		}
		else{
			llo ans=1;
			cout<<max(pre[j/2],ans)<<endl;
		}
	}








 
	return 0;
}

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