제출 #543471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543471		alvingogo	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	584 ms	37020 KiB

meetings2

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define cd complex<double>
#define p_q priority_queue
using namespace std;

struct no{
	vector<int> ch;
	int as[20]={0};
	int dep=-1;
	int sz;
};
vector<no> v;
void dfs(int r,int f){
	v[r].dep=v[f].dep+1;
	v[r].as[0]=f;
	v[r].sz=1;
	for(auto h:v[r].ch){
		if(h!=f){
			dfs(h,r);
			v[r].sz+=v[h].sz;
		}
	}
}
void gas(int n){
	for(int i=1;i<20;i++){
		for(int j=0;j<n;j++){
			v[j].as[i]=v[v[j].as[i-1]].as[i-1];
		}
	}
}
int fc(int r,int f,int nz){
	for(auto h:v[r].ch){
		if(h!=f){
			if(v[h].sz>nz/2){
				return fc(h,r,nz);
			}
		}
	}
	return r;
}
int dia=0,cz,e=0,f=0;
int lca(int x,int y){
	if(v[x].dep<v[y].dep){
		swap(x,y);
	}
	for(int i=19;i>=0;i--){
		if(v[v[x].as[i]].dep>=v[y].dep){
			x=v[x].as[i];
		}
	}
	if(x==y){
		return x;
	}
	for(int i=19;i>=0;i--){
		if(v[x].as[i]!=v[y].as[i]){
			x=v[x].as[i];
			y=v[y].as[i];
		}	
	}
	return v[x].as[0];
}
int dis(int x,int y){
	int u=lca(x,y);
	return v[x].dep+v[y].dep-2*v[u].dep;
}
void add(int z){
	int x=dis(z,e);
	int y=dis(z,f);
	int a,b;
	if(x>y){
		a=e;
		b=x;
	}
	else{
		a=f;
		b=y;
	}
	if(b>dia){
		dia=b;
		if(e==a){
			f=z;
		}
		else{
			e=z;
		}
	}
}
int main(){
	AquA;
	int n;
	cin >> n;
	v.resize(n);
	for(int i=1;i<n;i++){
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		v[a].ch.push_back(b);
		v[b].ch.push_back(a);
	}
	dfs(0,0);
	int ct=fc(0,0,n);
	dfs(ct,ct);
	gas(n);
	vector<pair<int,int> > vp;
	for(int i=0;i<n;i++){
		vp.push_back({v[i].sz,i});
	}	
	sort(vp.begin(),vp.end(),greater<pair<int,int> >());
	vector<int> ans(n+1);
	e=ct;
	f=ct;
	cz=1;
	for(int i=1;i<=n;i+=2){
		ans[i]=1;
	}
	for(int i=n-n%2;i>=2;i-=2){
		while(cz<n){
			if(vp[cz].fs<i/2){
				break;
			}
			add(vp[cz].sc);
			cz++;
		}
		ans[i]=dia+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