oj.uz

Submission #572678

# Submission time Handle Problem Language Result Execution time Memory
572678 2022-06-05T03:05:46 Z Arvin Meetings 2 (JOI21_meetings2) C++17
0 / 100
 3 ms 5076 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -