제출 #1361583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361583		Jawad_Akbar_JJ	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	1 ms	344 KiB

meetings2

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1<<18;
vector<int> nei[N];
vector<pair<int, int>> vec;
int Mx[N][2], ch[N];

void dfs(int u, int p){
	ch[u] = 1;
	for (int i : nei[u]){
		if (i != p)
			dfs(i, u), ch[u] += ch[i];
	}
}

int cent(int u, int p, int n){
	for (int i : nei[u]){
		if (i != p and ch[i] + ch[i] > n)
			return cent(i, u, n);
	}
	return u;
}

void Dfs(int u, int p, int h){
	vec.push_back({ch[u], h});
	for (int i : nei[u]){
		if (i != p)
			Dfs(i, u, h+1);
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n;
	cin>>n;

	for (int i=1, a, b;i<n;i++){
		cin>>a>>b;

		nei[a].push_back(b);
		nei[b].push_back(a);
	}



	dfs(1, 0);
	int C = cent(1, 0, n);
	dfs(C, 0);

	for (int i : nei[C]){
		Dfs(i, C, 1);

		sort(begin(vec), end(vec));

		auto [sz, h] = vec.back();
		for (int j=sz; j; j--){
			while (vec.size() > 0 and vec.back().first  == j)
				h = max(h, vec.back().second), vec.pop_back();
			if (Mx[j][0] < h)
				Mx[j][1] = Mx[j][0], Mx[j][0] = h;
			else if (Mx[j][1] < h)
				Mx[j][1] = h;
		}
	}

	for (int i=1;i<=n;i++){
		if (i & 1)
			cout<<"1\n";
		else
			cout<<Mx[i / 2][0] + Mx[i / 2][1] + 1<<'\n';
	}
}

• 서브태스크 1: 0 / 4
• 서브태스크 2: 0 / 16
• 서브태스크 3: 0 / 80