91552024-02-16 15:22:56111Hosszú Láncokcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz3ms1832 KiB
2Hibás válasz3ms2056 KiB
3Hibás válasz3ms2428 KiB
4Hibás válasz3ms2544 KiB
subtask20/10
5Elfogadva2ms2572 KiB
6Hibás válasz3ms2680 KiB
7Hibás válasz3ms2904 KiB
8Hibás válasz3ms2988 KiB
9Elfogadva3ms3224 KiB
10Hibás válasz3ms3348 KiB
11Hibás válasz3ms3400 KiB
12Hibás válasz3ms3520 KiB
13Hibás válasz3ms3732 KiB
14Hibás válasz3ms3844 KiB
15Hibás válasz3ms3968 KiB
subtask30/20
16Hibás válasz3ms4052 KiB
17Hibás válasz3ms4132 KiB
18Hibás válasz3ms4256 KiB
19Hibás válasz3ms4388 KiB
20Hibás válasz3ms4552 KiB
21Hibás válasz3ms4724 KiB
22Hibás válasz3ms4716 KiB
23Hibás válasz4ms4824 KiB
subtask40/20
24Hibás válasz3ms4824 KiB
25Hibás válasz3ms4920 KiB
26Hibás válasz4ms4984 KiB
27Hibás válasz4ms4880 KiB
28Hibás válasz3ms4824 KiB
29Hibás válasz4ms4844 KiB
30Hibás válasz6ms4936 KiB
31Hibás válasz14ms4912 KiB
subtask50/50
32Hibás válasz18ms6024 KiB
33Hibás válasz59ms6976 KiB
34Hibás válasz130ms10744 KiB
35Hibás válasz160ms16716 KiB
36Hibás válasz54ms5936 KiB
37Hibás válasz268ms7100 KiB
38Hibás válasz282ms10868 KiB
39Hibás válasz411ms16572 KiB