9156 | 2024-02-16 15:23:31 | 111 | Hosszú Láncok | cpp17 | Hibás válasz 10/100 | 72ms | 16124 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1832 KiB | ||||
2 | Elfogadva | 3ms | 2060 KiB | ||||
3 | Elfogadva | 3ms | 2104 KiB | ||||
4 | Elfogadva | 3ms | 2236 KiB | ||||
subtask2 | 10/10 | ||||||
5 | Elfogadva | 3ms | 2452 KiB | ||||
6 | Elfogadva | 3ms | 2672 KiB | ||||
7 | Elfogadva | 3ms | 2868 KiB | ||||
8 | Elfogadva | 3ms | 3076 KiB | ||||
9 | Elfogadva | 3ms | 3292 KiB | ||||
10 | Elfogadva | 3ms | 3640 KiB | ||||
11 | Elfogadva | 3ms | 3636 KiB | ||||
12 | Elfogadva | 3ms | 3640 KiB | ||||
13 | Elfogadva | 3ms | 3732 KiB | ||||
14 | Elfogadva | 3ms | 3864 KiB | ||||
15 | Elfogadva | 3ms | 3744 KiB | ||||
subtask3 | 0/20 | ||||||
16 | Elfogadva | 3ms | 3868 KiB | ||||
17 | Elfogadva | 3ms | 3972 KiB | ||||
18 | Elfogadva | 3ms | 3968 KiB | ||||
19 | Elfogadva | 3ms | 4192 KiB | ||||
20 | Elfogadva | 3ms | 4176 KiB | ||||
21 | Elfogadva | 3ms | 4180 KiB | ||||
22 | Hibás válasz | 3ms | 4404 KiB | ||||
23 | Hibás válasz | 3ms | 4508 KiB | ||||
subtask4 | 0/20 | ||||||
24 | Elfogadva | 3ms | 4348 KiB | ||||
25 | Elfogadva | 3ms | 4368 KiB | ||||
26 | Elfogadva | 3ms | 4392 KiB | ||||
27 | Hibás válasz | 3ms | 4380 KiB | ||||
28 | Hibás válasz | 3ms | 4264 KiB | ||||
29 | Hibás válasz | 3ms | 4388 KiB | ||||
30 | Hibás válasz | 3ms | 4480 KiB | ||||
31 | Hibás válasz | 3ms | 4500 KiB | ||||
subtask5 | 0/50 | ||||||
32 | Hibás válasz | 7ms | 5468 KiB | ||||
33 | Elfogadva | 13ms | 6504 KiB | ||||
34 | Elfogadva | 30ms | 10272 KiB | ||||
35 | Elfogadva | 59ms | 16124 KiB | ||||
36 | Hibás válasz | 10ms | 5592 KiB | ||||
37 | Hibás válasz | 20ms | 6632 KiB | ||||
38 | Hibás válasz | 46ms | 10400 KiB | ||||
39 | Hibás válasz | 72ms | 16124 KiB |