91562024-02-16 15:23:31111Hosszú Láncokcpp17Hibás válasz 10/10072ms16124 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);
				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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1832 KiB
2Elfogadva3ms2060 KiB
3Elfogadva3ms2104 KiB
4Elfogadva3ms2236 KiB
subtask210/10
5Elfogadva3ms2452 KiB
6Elfogadva3ms2672 KiB
7Elfogadva3ms2868 KiB
8Elfogadva3ms3076 KiB
9Elfogadva3ms3292 KiB
10Elfogadva3ms3640 KiB
11Elfogadva3ms3636 KiB
12Elfogadva3ms3640 KiB
13Elfogadva3ms3732 KiB
14Elfogadva3ms3864 KiB
15Elfogadva3ms3744 KiB
subtask30/20
16Elfogadva3ms3868 KiB
17Elfogadva3ms3972 KiB
18Elfogadva3ms3968 KiB
19Elfogadva3ms4192 KiB
20Elfogadva3ms4176 KiB
21Elfogadva3ms4180 KiB
22Hibás válasz3ms4404 KiB
23Hibás válasz3ms4508 KiB
subtask40/20
24Elfogadva3ms4348 KiB
25Elfogadva3ms4368 KiB
26Elfogadva3ms4392 KiB
27Hibás válasz3ms4380 KiB
28Hibás válasz3ms4264 KiB
29Hibás válasz3ms4388 KiB
30Hibás válasz3ms4480 KiB
31Hibás válasz3ms4500 KiB
subtask50/50
32Hibás válasz7ms5468 KiB
33Elfogadva13ms6504 KiB
34Elfogadva30ms10272 KiB
35Elfogadva59ms16124 KiB
36Hibás válasz10ms5592 KiB
37Hibás válasz20ms6632 KiB
38Hibás válasz46ms10400 KiB
39Hibás válasz72ms16124 KiB