9157 | 2024-02-16 15:28:27 | 111 | Hosszú Láncok | cpp17 | Accepted 100/100 | 119ms | 16748 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;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1828 KiB | ||||
2 | Accepted | 3ms | 2052 KiB | ||||
3 | Accepted | 3ms | 2232 KiB | ||||
4 | Accepted | 3ms | 2444 KiB | ||||
subtask2 | 10/10 | ||||||
5 | Accepted | 3ms | 2656 KiB | ||||
6 | Accepted | 3ms | 2868 KiB | ||||
7 | Accepted | 3ms | 2952 KiB | ||||
8 | Accepted | 2ms | 2952 KiB | ||||
9 | Accepted | 2ms | 2948 KiB | ||||
10 | Accepted | 2ms | 2948 KiB | ||||
11 | Accepted | 3ms | 3100 KiB | ||||
12 | Accepted | 3ms | 3148 KiB | ||||
13 | Accepted | 3ms | 3284 KiB | ||||
14 | Accepted | 3ms | 3260 KiB | ||||
15 | Accepted | 3ms | 3268 KiB | ||||
subtask3 | 20/20 | ||||||
16 | Accepted | 3ms | 3364 KiB | ||||
17 | Accepted | 3ms | 3360 KiB | ||||
18 | Accepted | 3ms | 3264 KiB | ||||
19 | Accepted | 3ms | 3396 KiB | ||||
20 | Accepted | 3ms | 3600 KiB | ||||
21 | Accepted | 3ms | 3940 KiB | ||||
22 | Accepted | 3ms | 3940 KiB | ||||
23 | Accepted | 3ms | 3848 KiB | ||||
subtask4 | 20/20 | ||||||
24 | Accepted | 3ms | 3836 KiB | ||||
25 | Accepted | 3ms | 3916 KiB | ||||
26 | Accepted | 3ms | 4032 KiB | ||||
27 | Accepted | 3ms | 4320 KiB | ||||
28 | Accepted | 3ms | 4344 KiB | ||||
29 | Accepted | 3ms | 4428 KiB | ||||
30 | Accepted | 3ms | 4532 KiB | ||||
31 | Accepted | 3ms | 4836 KiB | ||||
subtask5 | 50/50 | ||||||
32 | Accepted | 7ms | 6004 KiB | ||||
33 | Accepted | 13ms | 7032 KiB | ||||
34 | Accepted | 28ms | 10772 KiB | ||||
35 | Accepted | 59ms | 16736 KiB | ||||
36 | Accepted | 9ms | 5972 KiB | ||||
37 | Accepted | 19ms | 7132 KiB | ||||
38 | Accepted | 64ms | 10900 KiB | ||||
39 | Accepted | 119ms | 16748 KiB |