oj.uz

Submission #538510

# Submission time Handle Problem Language Result Execution time Memory
538510 2022-03-17T03:34:08 Z pavement Meetings 2 (JOI21_meetings2) C++17
100 / 100
 636 ms 68556 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;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, cur, root, dep[200005], sz[200005], ans[200005], anc[200005][25];
ii T[200005];
vector<int> adj[200005];

int dfs(int n, int e = -1) {
	int s = 1, m = 0;
	for (auto u : adj[n]) if (u != e) {
		int tmp = dfs(u, n);
		s += tmp;
		m = max(m, tmp);
	}
	m = max(m, N - s);
	if (m <= N / 2) root = n;
	return s;
}

int init(int n, int e = -1) {
	anc[n][0] = e;
	sz[n] = 1;
	for (auto u : adj[n]) if (u != e) {
		dep[u] = dep[n] + 1;
		sz[n] += init(u, n);
	}
	return sz[n];
}

int lca(int u, int v) {
	if (dep[u] > dep[v]) swap(u, v);
	for (int i = 20; i >= 0; i--)
		if (anc[v][i] != -1 && dep[anc[v][i]] >= dep[u]) v = anc[v][i];
	if (u == v) return u;
	for (int i = 20; i >= 0; i--)
		if (anc[u][i] != -1 && anc[v][i] != -1 && anc[u][i] != anc[v][i]) {
			u = anc[u][i];
			v = anc[v][i];
		}
	return anc[u][0];
}

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

main() {
	memset(anc, -1, sizeof anc);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1, u, v; i < N; i++) {
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1);
	assert(root);
	init(root);
	for (int k = 1; k <= 20; k++)
		for (int i = 1; i <= N; i++)
			if (anc[i][k - 1] != -1) anc[i][k] = anc[anc[i][k - 1]][k - 1];
	for (int i = 1; i <= N; i++) T[i] = mp(sz[i], i);
	sort(T + 1, T + 1 + N, greater<ii>());
	for (int i = 1, ed1, ed2; i <= N; i++) {
		if (i == 1) {
			ed1 = ed2 = T[i].second;
			ans[T[i].first] = max(ans[T[i].first], 1ll);
			continue;
		}
		iii tmp = max({mt(dist(ed1, ed2), ed1, ed2), mt(dist(ed1, T[i].second), ed1, T[i].second), mt(dist(ed2, T[i].second), ed2, T[i].second)});
		ed1 = g1(tmp);
		ed2 = g2(tmp);
		ans[T[i].first] = max(ans[T[i].first], g0(tmp) + 1);
	}
	for (int i = N; i >= 1; i--) ans[i] = max(ans[i], ans[i + 1]);
	for (int i = 1; i <= N; i++)
		if (i & 1) cout << "1\n";
		else cout << ans[i / 2] << '\n';
}

Compilation message

meetings2.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main() {
      | ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 44116 KB Output is correct
2 Correct 19 ms 44080 KB Output is correct
3 Correct 20 ms 44116 KB Output is correct
4 Correct 20 ms 44116 KB Output is correct
5 Correct 23 ms 44064 KB Output is correct
6 Correct 20 ms 44128 KB Output is correct
7 Correct 20 ms 44252 KB Output is correct
8 Correct 19 ms 44116 KB Output is correct
9 Correct 20 ms 44148 KB Output is correct
10 Correct 20 ms 44116 KB Output is correct
11 Correct 23 ms 44180 KB Output is correct
12 Correct 21 ms 44228 KB Output is correct
13 Correct 20 ms 44156 KB Output is correct
14 Correct 23 ms 44176 KB Output is correct
15 Correct 20 ms 44184 KB Output is correct
16 Correct 21 ms 44080 KB Output is correct
17 Correct 20 ms 44080 KB Output is correct
18 Correct 19 ms 44144 KB Output is correct
19 Correct 21 ms 44172 KB Output is correct
20 Correct 20 ms 44116 KB Output is correct
21 Correct 20 ms 44180 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 44116 KB Output is correct
2 Correct 19 ms 44080 KB Output is correct
3 Correct 20 ms 44116 KB Output is correct
4 Correct 20 ms 44116 KB Output is correct
5 Correct 23 ms 44064 KB Output is correct
6 Correct 20 ms 44128 KB Output is correct
7 Correct 20 ms 44252 KB Output is correct
8 Correct 19 ms 44116 KB Output is correct
9 Correct 20 ms 44148 KB Output is correct
10 Correct 20 ms 44116 KB Output is correct
11 Correct 23 ms 44180 KB Output is correct
12 Correct 21 ms 44228 KB Output is correct
13 Correct 20 ms 44156 KB Output is correct
14 Correct 23 ms 44176 KB Output is correct
15 Correct 20 ms 44184 KB Output is correct
16 Correct 21 ms 44080 KB Output is correct
17 Correct 20 ms 44080 KB Output is correct
18 Correct 19 ms 44144 KB Output is correct
19 Correct 21 ms 44172 KB Output is correct
20 Correct 20 ms 44116 KB Output is correct
21 Correct 20 ms 44180 KB Output is correct
22 Correct 29 ms 44496 KB Output is correct
23 Correct 23 ms 44544 KB Output is correct
24 Correct 25 ms 44528 KB Output is correct
25 Correct 22 ms 44500 KB Output is correct
26 Correct 23 ms 44528 KB Output is correct
27 Correct 23 ms 44540 KB Output is correct
28 Correct 27 ms 44496 KB Output is correct
29 Correct 30 ms 44496 KB Output is correct
30 Correct 23 ms 44492 KB Output is correct
31 Correct 24 ms 44500 KB Output is correct
32 Correct 26 ms 44504 KB Output is correct
33 Correct 23 ms 44604 KB Output is correct
34 Correct 22 ms 44440 KB Output is correct
35 Correct 23 ms 44440 KB Output is correct
36 Correct 24 ms 44456 KB Output is correct
37 Correct 25 ms 44440 KB Output is correct
38 Correct 24 ms 44508 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 44116 KB Output is correct
2 Correct 19 ms 44080 KB Output is correct
3 Correct 20 ms 44116 KB Output is correct
4 Correct 20 ms 44116 KB Output is correct
5 Correct 23 ms 44064 KB Output is correct
6 Correct 20 ms 44128 KB Output is correct
7 Correct 20 ms 44252 KB Output is correct
8 Correct 19 ms 44116 KB Output is correct
9 Correct 20 ms 44148 KB Output is correct
10 Correct 20 ms 44116 KB Output is correct
11 Correct 23 ms 44180 KB Output is correct
12 Correct 21 ms 44228 KB Output is correct
13 Correct 20 ms 44156 KB Output is correct
14 Correct 23 ms 44176 KB Output is correct
15 Correct 20 ms 44184 KB Output is correct
16 Correct 21 ms 44080 KB Output is correct
17 Correct 20 ms 44080 KB Output is correct
18 Correct 19 ms 44144 KB Output is correct
19 Correct 21 ms 44172 KB Output is correct
20 Correct 20 ms 44116 KB Output is correct
21 Correct 20 ms 44180 KB Output is correct
22 Correct 29 ms 44496 KB Output is correct
23 Correct 23 ms 44544 KB Output is correct
24 Correct 25 ms 44528 KB Output is correct
25 Correct 22 ms 44500 KB Output is correct
26 Correct 23 ms 44528 KB Output is correct
27 Correct 23 ms 44540 KB Output is correct
28 Correct 27 ms 44496 KB Output is correct
29 Correct 30 ms 44496 KB Output is correct
30 Correct 23 ms 44492 KB Output is correct
31 Correct 24 ms 44500 KB Output is correct
32 Correct 26 ms 44504 KB Output is correct
33 Correct 23 ms 44604 KB Output is correct
34 Correct 22 ms 44440 KB Output is correct
35 Correct 23 ms 44440 KB Output is correct
36 Correct 24 ms 44456 KB Output is correct
37 Correct 25 ms 44440 KB Output is correct
38 Correct 24 ms 44508 KB Output is correct
39 Correct 287 ms 62028 KB Output is correct
40 Correct 319 ms 61616 KB Output is correct
41 Correct 270 ms 62100 KB Output is correct
42 Correct 333 ms 62292 KB Output is correct
43 Correct 289 ms 62404 KB Output is correct
44 Correct 331 ms 62360 KB Output is correct
45 Correct 636 ms 66192 KB Output is correct
46 Correct 453 ms 68556 KB Output is correct
47 Correct 236 ms 62328 KB Output is correct
48 Correct 184 ms 62652 KB Output is correct
49 Correct 382 ms 62668 KB Output is correct
50 Correct 209 ms 62716 KB Output is correct
51 Correct 369 ms 68092 KB Output is correct