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