oj.uz

Submission #490238

# Submission time Handle Problem Language Result Execution time Memory
490238 2021-11-26T14:08:30 Z wind_reaper Meetings 2 (JOI21_meetings2) C++17
100 / 100
 445 ms 48196 KB 
#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/

using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;

// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

//***************** CONSTANTS *****************

const int MXN = 200001;
const int K = 20;

//***************** GLOBAL VARIABLES *****************

vector<int> g[MXN], leaf[MXN];
int up[K][MXN], sub[MXN], tin[MXN], tout[MXN], timer, depth[MXN], ans[MXN], counter[MXN];
bool added[MXN];

//***************** AUXILIARY STRUCTS *****************

void dfs(int p, int u){
	depth[u] = depth[p] + 1;
	tin[u] = timer++;

	up[0][u] = p;

	for(int i = 1; i < K; i++)
		up[i][u] = up[i-1][up[i-1][u]];

	for(int v : g[u]) if(v != p){
		dfs(u, v);
	}

	tout[u] = timer++;
}

bool check(int u, int v){
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v){
	if(check(u, v)) return u;
	if(check(v, u)) return v;

	for(int i = K - 1; i >= 0; --i){
		if(!check(up[i][u], v))
			u = up[i][u];
	}

	return up[0][u];
}

int dist(int u, int v){
	return depth[u] + depth[v] - 2*depth[lca(u, v)];
}

//***************** MAIN BODY *****************

void solve(){
	int N;
	cin >> N;

	for(int i = 0; i < N - 1; i++){
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	dfs(1, 1);

	for(int i = 1; i <= N; i++)
		if(g[i].size() == 1){
			leaf[1].push_back(i);
			added[i] = 1;
		}

	fill(sub + 1, sub + N + 1, 1);

	for(int s = 1; s <= N; s++) for(int u : leaf[s]) for(int v : g[u]){
		if(added[v]) continue;
		counter[v]++;

		sub[v] += sub[u];

		if(counter[v] == (int)g[v].size() - 1){
			added[v] = 1;
			leaf[sub[v]].push_back(v);
		}
	}

	array<int, 2> e = {-1, -1};
	int j = N >> 1;

	fill(ans + 1, ans + N + 1, 1);

	for(int s = N; s >= 1; --s) for(int x : leaf[s]){
		if(e[0] == -1)
			e[0] = x;
		else if(e[1] == -1)
			e[1] = x;
		else{
			if(dist(e[0], x) > dist(e[0], e[1])) e[1] = x;
			else if(dist(e[1], x) > dist(e[0], e[1])) e[0] = x;
		}

		if(e[1] == -1) continue;

		while(j > min(sub[e[0]], sub[e[1]]))
			--j;

		ans[2*j] = dist(e[0], e[1]) + 1;
	}


	for(int i = N - (N & 1) - 2; i >= 2; i -= 2)
		ans[i] = max(ans[i], ans[i + 2]);

	for(int i = 1; i <= N; i++)
		cout << ans[i] << '\n';
}

//***************** *****************

int32_t main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);

	#ifdef LOCAL
		auto begin = high_resolution_clock::now();
	#endif

	int tc = 1;
	// cin >> tc; 
	for (int t = 0; t < tc; t++)
		solve();

	#ifdef LOCAL 
		auto end = high_resolution_clock::now();
		cout << fixed << setprecision(4);
		cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
	#endif

	return 0;
}

/*
If code gives a WA, check for the following : 
1. I/O format

2. Are you clearing all global variables in between tests if multitests are a thing

3. Can you definitively prove the logic

4. If the code gives an inexplicable TLE, and you are sure you have the best possible complexity,
use faster io
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9804 KB Output is correct
2 Correct 5 ms 9764 KB Output is correct
3 Correct 6 ms 9788 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Correct 5 ms 9804 KB Output is correct
6 Correct 5 ms 9804 KB Output is correct
7 Correct 5 ms 9804 KB Output is correct
8 Correct 4 ms 9804 KB Output is correct
9 Correct 5 ms 9804 KB Output is correct
10 Correct 5 ms 9804 KB Output is correct
11 Correct 4 ms 9804 KB Output is correct
12 Correct 6 ms 9804 KB Output is correct
13 Correct 5 ms 9804 KB Output is correct
14 Correct 5 ms 9804 KB Output is correct
15 Correct 5 ms 9844 KB Output is correct
16 Correct 5 ms 9804 KB Output is correct
17 Correct 5 ms 9804 KB Output is correct
18 Correct 5 ms 9804 KB Output is correct
19 Correct 5 ms 9776 KB Output is correct
20 Correct 5 ms 9804 KB Output is correct
21 Correct 6 ms 9804 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9804 KB Output is correct
2 Correct 5 ms 9764 KB Output is correct
3 Correct 6 ms 9788 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Correct 5 ms 9804 KB Output is correct
6 Correct 5 ms 9804 KB Output is correct
7 Correct 5 ms 9804 KB Output is correct
8 Correct 4 ms 9804 KB Output is correct
9 Correct 5 ms 9804 KB Output is correct
10 Correct 5 ms 9804 KB Output is correct
11 Correct 4 ms 9804 KB Output is correct
12 Correct 6 ms 9804 KB Output is correct
13 Correct 5 ms 9804 KB Output is correct
14 Correct 5 ms 9804 KB Output is correct
15 Correct 5 ms 9844 KB Output is correct
16 Correct 5 ms 9804 KB Output is correct
17 Correct 5 ms 9804 KB Output is correct
18 Correct 5 ms 9804 KB Output is correct
19 Correct 5 ms 9776 KB Output is correct
20 Correct 5 ms 9804 KB Output is correct
21 Correct 6 ms 9804 KB Output is correct
22 Correct 8 ms 10464 KB Output is correct
23 Correct 8 ms 10444 KB Output is correct
24 Correct 11 ms 10368 KB Output is correct
25 Correct 8 ms 10444 KB Output is correct
26 Correct 8 ms 10444 KB Output is correct
27 Correct 8 ms 10444 KB Output is correct
28 Correct 7 ms 10444 KB Output is correct
29 Correct 8 ms 10444 KB Output is correct
30 Correct 9 ms 10444 KB Output is correct
31 Correct 8 ms 10364 KB Output is correct
32 Correct 8 ms 10572 KB Output is correct
33 Correct 8 ms 10572 KB Output is correct
34 Correct 8 ms 10468 KB Output is correct
35 Correct 7 ms 10444 KB Output is correct
36 Correct 7 ms 10444 KB Output is correct
37 Correct 8 ms 10444 KB Output is correct
38 Correct 8 ms 10444 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9804 KB Output is correct
2 Correct 5 ms 9764 KB Output is correct
3 Correct 6 ms 9788 KB Output is correct
4 Correct 5 ms 9804 KB Output is correct
5 Correct 5 ms 9804 KB Output is correct
6 Correct 5 ms 9804 KB Output is correct
7 Correct 5 ms 9804 KB Output is correct
8 Correct 4 ms 9804 KB Output is correct
9 Correct 5 ms 9804 KB Output is correct
10 Correct 5 ms 9804 KB Output is correct
11 Correct 4 ms 9804 KB Output is correct
12 Correct 6 ms 9804 KB Output is correct
13 Correct 5 ms 9804 KB Output is correct
14 Correct 5 ms 9804 KB Output is correct
15 Correct 5 ms 9844 KB Output is correct
16 Correct 5 ms 9804 KB Output is correct
17 Correct 5 ms 9804 KB Output is correct
18 Correct 5 ms 9804 KB Output is correct
19 Correct 5 ms 9776 KB Output is correct
20 Correct 5 ms 9804 KB Output is correct
21 Correct 6 ms 9804 KB Output is correct
22 Correct 8 ms 10464 KB Output is correct
23 Correct 8 ms 10444 KB Output is correct
24 Correct 11 ms 10368 KB Output is correct
25 Correct 8 ms 10444 KB Output is correct
26 Correct 8 ms 10444 KB Output is correct
27 Correct 8 ms 10444 KB Output is correct
28 Correct 7 ms 10444 KB Output is correct
29 Correct 8 ms 10444 KB Output is correct
30 Correct 9 ms 10444 KB Output is correct
31 Correct 8 ms 10364 KB Output is correct
32 Correct 8 ms 10572 KB Output is correct
33 Correct 8 ms 10572 KB Output is correct
34 Correct 8 ms 10468 KB Output is correct
35 Correct 7 ms 10444 KB Output is correct
36 Correct 7 ms 10444 KB Output is correct
37 Correct 8 ms 10444 KB Output is correct
38 Correct 8 ms 10444 KB Output is correct
39 Correct 270 ms 40064 KB Output is correct
40 Correct 242 ms 39404 KB Output is correct
41 Correct 282 ms 40056 KB Output is correct
42 Correct 269 ms 40544 KB Output is correct
43 Correct 268 ms 40536 KB Output is correct
44 Correct 258 ms 40448 KB Output is correct
45 Correct 445 ms 45400 KB Output is correct
46 Correct 426 ms 48196 KB Output is correct
47 Correct 252 ms 40980 KB Output is correct
48 Correct 175 ms 40284 KB Output is correct
49 Correct 235 ms 41220 KB Output is correct
50 Correct 208 ms 40836 KB Output is correct
51 Correct 222 ms 46696 KB Output is correct