91552024-02-16 15:22:56111Hosszú Láncokcpp17Wrong answer 0/100411ms16716 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef CB
	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
	int N;
	cin >> N;
	vector<vector<int>> g(N + 1);
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	auto dfs = [&](auto dfs, int i) -> void {
		for (int j : g[i]) {
			g[j].erase(find(g[j].begin(), g[j].end(), i));
			dfs(dfs, j);
		}
	};
	dfs(dfs, 1);
	int l = 2, h = N;
	while (l != h) {
		int m = (l + h) / 2;
		auto dfs = [&](auto dfs, int i) -> int {
			multiset<int> s;
			int c = 0;
			for (int j : g[i]) {
				int r = dfs(dfs, j);
				cout<<j<< " "<<r<<endl;
				if (r == -1) {
					return -1;
				}
				if (r + 1 == m) {
					c++;
				}
				else {
					s.insert(r);
				}
			}
			vector<int> v;
			while (!s.empty()) {
				int x = *s.begin();
				s.erase(s.begin());
				auto t = s.lower_bound(m - x - 2);
				if (t == s.end()) {
					if (v.size() >= 1 && c > 0) {
						c--;
					}
					else {
						v.push_back(x);
					}
					continue;
				}
				s.erase(t);
			}
			if (v.size() >= 2) {
				return -1;
			}
			if (c >= 2) {
				return m;
			}
			if (v.size() == 1) {
				return i == 1 && c == 1 ? 0 : v[0] + 1;
			}
			return c > 0 ? m : 0;
		};
		int ans = dfs(dfs, 1);
		if (ans == -1 || ans > 0 && ans < m) {
			h = m;
		}
		else {
			l = m + 1;
		}
	}
	cout << l - 1 << '\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer3ms1832 KiB
2Wrong answer3ms2056 KiB
3Wrong answer3ms2428 KiB
4Wrong answer3ms2544 KiB
subtask20/10
5Accepted2ms2572 KiB
6Wrong answer3ms2680 KiB
7Wrong answer3ms2904 KiB
8Wrong answer3ms2988 KiB
9Accepted3ms3224 KiB
10Wrong answer3ms3348 KiB
11Wrong answer3ms3400 KiB
12Wrong answer3ms3520 KiB
13Wrong answer3ms3732 KiB
14Wrong answer3ms3844 KiB
15Wrong answer3ms3968 KiB
subtask30/20
16Wrong answer3ms4052 KiB
17Wrong answer3ms4132 KiB
18Wrong answer3ms4256 KiB
19Wrong answer3ms4388 KiB
20Wrong answer3ms4552 KiB
21Wrong answer3ms4724 KiB
22Wrong answer3ms4716 KiB
23Wrong answer4ms4824 KiB
subtask40/20
24Wrong answer3ms4824 KiB
25Wrong answer3ms4920 KiB
26Wrong answer4ms4984 KiB
27Wrong answer4ms4880 KiB
28Wrong answer3ms4824 KiB
29Wrong answer4ms4844 KiB
30Wrong answer6ms4936 KiB
31Wrong answer14ms4912 KiB
subtask50/50
32Wrong answer18ms6024 KiB
33Wrong answer59ms6976 KiB
34Wrong answer130ms10744 KiB
35Wrong answer160ms16716 KiB
36Wrong answer54ms5936 KiB
37Wrong answer268ms7100 KiB
38Wrong answer282ms10868 KiB
39Wrong answer411ms16572 KiB