oj.uz

Submission #538281

# Submission time Handle Problem Language Result Execution time Memory
538281 2022-03-16T13:28:39 Z pavement Meetings 2 (JOI21_meetings2) C++17
0 / 100
 3 ms 5036 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 get_sz(int n, int e = -1) {
	anc[n][0] = (e == -1 ? n : e);
	sz[n] = 1;
	for (auto u : adj[n]) if (u != e) {
		dep[u] = dep[n] + 1;
		sz[n] += get_sz(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 (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] != 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() {
	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);
	get_sz(root);
	for (int k = 20; k >= 0; k--)
		for (int i = 1; i <= N; i++)
			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;
		}
		// add node T[i].second
		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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5028 KB Output is correct
9 Correct 3 ms 5028 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Incorrect 3 ms 4948 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5028 KB Output is correct
9 Correct 3 ms 5028 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Incorrect 3 ms 4948 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5028 KB Output is correct
9 Correct 3 ms 5028 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Incorrect 3 ms 4948 KB Output isn't correct
12 Halted 0 ms 0 KB -