9155 | 2024-02-16 15:22:56 | 111 | Hosszú Láncok | cpp17 | Wrong answer 0/100 | 411ms | 16716 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;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Wrong answer | 3ms | 1832 KiB | ||||
2 | Wrong answer | 3ms | 2056 KiB | ||||
3 | Wrong answer | 3ms | 2428 KiB | ||||
4 | Wrong answer | 3ms | 2544 KiB | ||||
subtask2 | 0/10 | ||||||
5 | Accepted | 2ms | 2572 KiB | ||||
6 | Wrong answer | 3ms | 2680 KiB | ||||
7 | Wrong answer | 3ms | 2904 KiB | ||||
8 | Wrong answer | 3ms | 2988 KiB | ||||
9 | Accepted | 3ms | 3224 KiB | ||||
10 | Wrong answer | 3ms | 3348 KiB | ||||
11 | Wrong answer | 3ms | 3400 KiB | ||||
12 | Wrong answer | 3ms | 3520 KiB | ||||
13 | Wrong answer | 3ms | 3732 KiB | ||||
14 | Wrong answer | 3ms | 3844 KiB | ||||
15 | Wrong answer | 3ms | 3968 KiB | ||||
subtask3 | 0/20 | ||||||
16 | Wrong answer | 3ms | 4052 KiB | ||||
17 | Wrong answer | 3ms | 4132 KiB | ||||
18 | Wrong answer | 3ms | 4256 KiB | ||||
19 | Wrong answer | 3ms | 4388 KiB | ||||
20 | Wrong answer | 3ms | 4552 KiB | ||||
21 | Wrong answer | 3ms | 4724 KiB | ||||
22 | Wrong answer | 3ms | 4716 KiB | ||||
23 | Wrong answer | 4ms | 4824 KiB | ||||
subtask4 | 0/20 | ||||||
24 | Wrong answer | 3ms | 4824 KiB | ||||
25 | Wrong answer | 3ms | 4920 KiB | ||||
26 | Wrong answer | 4ms | 4984 KiB | ||||
27 | Wrong answer | 4ms | 4880 KiB | ||||
28 | Wrong answer | 3ms | 4824 KiB | ||||
29 | Wrong answer | 4ms | 4844 KiB | ||||
30 | Wrong answer | 6ms | 4936 KiB | ||||
31 | Wrong answer | 14ms | 4912 KiB | ||||
subtask5 | 0/50 | ||||||
32 | Wrong answer | 18ms | 6024 KiB | ||||
33 | Wrong answer | 59ms | 6976 KiB | ||||
34 | Wrong answer | 130ms | 10744 KiB | ||||
35 | Wrong answer | 160ms | 16716 KiB | ||||
36 | Wrong answer | 54ms | 5936 KiB | ||||
37 | Wrong answer | 268ms | 7100 KiB | ||||
38 | Wrong answer | 282ms | 10868 KiB | ||||
39 | Wrong answer | 411ms | 16572 KiB |