제출 #572678

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572678		Arvin	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	3 ms	5076 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int maxN = 2e5 + 5;

vector<int> adj[maxN];

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	
	int n;
	cin >> n;
	
	for(int x=0;x<n-1;x++){
		int a, b;
		cin >> a >> b;
		
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	auto dfs = [&](auto self, int curNode, int prvNode, int dist[]) -> void {
		for(auto nxt : adj[curNode]){
			if(nxt != prvNode){
				dist[nxt] = dist[curNode]+1;
				self(self, nxt, curNode, dist);
			}
		}
	};
	
	int dist[n];
	dist[0] = 0;
	dfs(dfs, 0, -1, dist);
	
	pair<int, int> mx = {0, 0};
	for(int x=0;x<n;x++){
		mx = max(mx, {dist[x], x});
	}
	
	dist[mx.second] = 0;
	dfs(dfs, mx.second, -1, dist);
	
	int diameter = 0;
	for(int x=0;x<n;x++){
		diameter = max(diameter, dist[x]+1);
	}
	
	for(int x=1;x<=n;x++){
		if(x&1){
			cout << "1\n";
		} else {
			if(x > diameter){
				cout << "2\n";
			} else {
				cout << diameter-x/2 * 2 + 2 << "\n";
			}
		}
	}
//	cout << diameter << " --\n";
    return 0;
}

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