oj.uz

답안 #543464

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
543464 2022-03-30T16:46:16 Z alvingogo Meetings 2 (JOI21_meetings2) C++14
0 / 100
 1 ms 596 KB 
#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;
		}
	}
}
int 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=0,e=0,f=0;
int lca(int x,int y){
	if(v[x].dep<v[y].dep){
		swap(x,y);
	}
	if(v[x].dep>=v[y].dep){
		for(int i=19;i>=0;i--){
			if(v[v[x].as[i]].dep>=v[y].dep){
				x=v[x].as[i];
			}
		}
	}
	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);
	add(ct);
	assert(vp[0].sc==ct);
	e=ct;
	f=ct;
	cz++;
	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;
}

Compilation message

meetings2.cpp: In function 'int gas(int)':
meetings2.cpp:34:1: warning: no return statement in function returning non-void [-Wreturn-type]
   34 | }
      | ^

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -