#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e6 + 7;
int n, tr, mo;
vector<int> g[N];
int par[N], cost[N];
bool vis[N];
void build_tree(int a, int p = -1) {
{
vector<int> Kids;
for (auto &b : g[a]) {
if (b != p) {
Kids.push_back(b);
}
}
g[a] = Kids;
}
for (auto &b : g[a]) {
build_tree(b, a);
}
par[a] = p;
}
void build_cost(int a) {
if (!vis[a] && a != mo) {
cost[a] += (int) g[a].size();
}
for (auto &b : g[a]) {
cost[b] += cost[a];
build_cost(b);
}
}
void dfs(int a) {
for (auto &b : g[a]) {
dfs(b);
}
if ((int) g[a].size() == 0) {
return;
}
if ((int) g[a].size() == 1) {
return;
}
assert((int) g[a].size() >= 2);
vector<int> Values;
for (auto &b : g[a]) {
Values.push_back(cost[b]);
}
sort(Values.rbegin(), Values.rend());
assert((int) Values.size() >= 2);
cost[a] = Values[1];
}
bool ok(int limit) {
vector<pair<int, int>> guys;
int dist = 0;
guys.push_back({0, cost[mo]});
int v = par[mo];
int sum = 0;
{
for (int i = 1; i <= n; i++) {
if ((vis[i] && i != tr) || i == mo) {
sum += (int) g[i].size() - 1;
}
}
sum++;
}
if (sum > limit) {
return 0;
}
while (v != tr) {
int skip = 0, cnt = 0;
for (auto &oth : g[v]) {
if (!vis[oth]) {
skip += (sum + cost[oth] <= limit);
cnt += (sum + cost[oth] > limit);
}
}
dist++;
sum -= skip;
if (cnt > dist) return 0;
v = par[v];
}
return 1;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
///freopen ("input.txt", "r", stdin);
cin >> n >> tr >> mo;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
build_tree(tr);
{
int current = par[mo];
while (current != tr) {
vis[current] = 1;
current = par[current];
}
vis[current] = 1;
}
build_cost(tr);
dfs(tr);
int low = 0, high = (int) 1e9 + 7, sol = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (ok(mid)) {
sol = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
assert(sol != -1);
cout << sol << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
13 ms |
23812 KB |
Output is correct |
4 |
Correct |
13 ms |
23744 KB |
Output is correct |
5 |
Correct |
12 ms |
23752 KB |
Output is correct |
6 |
Correct |
22 ms |
23764 KB |
Output is correct |
7 |
Incorrect |
13 ms |
23816 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
470 ms |
62868 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
13 ms |
23812 KB |
Output is correct |
4 |
Correct |
13 ms |
23744 KB |
Output is correct |
5 |
Correct |
12 ms |
23752 KB |
Output is correct |
6 |
Correct |
22 ms |
23764 KB |
Output is correct |
7 |
Incorrect |
13 ms |
23816 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
13 ms |
23812 KB |
Output is correct |
4 |
Correct |
13 ms |
23744 KB |
Output is correct |
5 |
Correct |
12 ms |
23752 KB |
Output is correct |
6 |
Correct |
22 ms |
23764 KB |
Output is correct |
7 |
Incorrect |
13 ms |
23816 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |