#include <bits/stdc++.h>
using namespace std;
template <typename T> T load() { T r; cin >> r; return r; }
template <typename T> vector<T> loadMany(int n) { vector<T> rs(n); generate(rs.begin(), rs.end(), &load<T>); return rs; }
struct Dummyf { template <typename... Ts> void operator()(Ts&&...) {} };
template <typename T, typename F> T binsearch(T a, T b, F f) {
if (b - a == 0) return a;
if (b - a == 1) return f(a) ? a : b;
auto m = (a+b)/2;
return f(m) ? binsearch(a, m, f) : binsearch(m+1, b, f);
}
struct Graph {
Graph(int n):edges(n){}
void addEdge1(int a, int b) { edges[a].push_back(b); }
void addEdge2(int a, int b) { addEdge1(a, b); addEdge1(b, a); }
int size() const { return (int)edges.size(); }
template <typename Pre=Dummyf, typename Post=Dummyf, typename PreE=Dummyf, typename PostE=Dummyf, typename FailE=Dummyf> void DFS(int source, Pre pre, Post post, PreE pree, PostE poste, FailE faile) const {
auto visit = vector<bool>(size(), false);
implDFS(source, visit, pre, post, pree, poste, faile);
}
template <typename Pre=Dummyf, typename Post=Dummyf, typename PreE=Dummyf, typename PostE=Dummyf, typename FailE=Dummyf> void implDFS(int v, vector<bool>& visit, Pre pre, Post post, PreE pree, PostE poste, FailE faile) const {
visit[v] = true;
pre(v);
for (auto u : edges[v])
if (not visit[u])
pree(v, u), implDFS(u, visit, pre, post, pree, poste, faile), poste(v, u);
else
faile(v, u);
post(v);
}
vector<vector<int>> edges;
};
Graph loadEdges(int n, int m) {
auto g = Graph(n);
while (m --> 0)
g.addEdge2(load<int>()-1, load<int>()-1);
return g;
}
struct Roots {
vector<bool> is;
vector<int> vertices;
};
Roots researchRoots(int s1, int s2, int n, const Graph& tree) {
auto root = vector<bool>(n, false);
auto path = vector<int>({s2});
root[s2] = true;
tree.DFS(s1, {}, {}, {}, [&](int v, int u){
if (root[u]) {
root[v] = true;
path.push_back(v);
}
}, {});
reverse(path.begin(), path.end());
return Roots{move(root), move(path)};
}
struct Cell {
int requirement;
vector<int> kids;
};
void partDynamic(int src, vector<bool>& visit, vector<Cell>& dyn, const Graph& tree) {
tree.implDFS(src, visit, {}, [&](int v){
sort(dyn[v].kids.begin(), dyn[v].kids.end(), [&](int u1, int u2) {
return dyn[u1].requirement < dyn[u2].requirement;
});
dyn[v].requirement = 0;
for (auto t=0; t<(int)dyn[v].kids.size(); ++t) {
auto u = dyn[v].kids[(int)(dyn[v].kids.size())-t-1];
dyn[v].requirement = max(dyn[v].requirement, t + 1 + dyn[u].requirement);
}
}, [&](int v, int u){
dyn[v].kids.push_back(u);
}, {}, {});
}
vector<Cell> brutCutDyn(int s1, int s2, int smr, int n, const Graph& tree, const Roots& root) {
auto dyn = vector<Cell>(n, Cell{-1});
auto visit = vector<bool>(n, false);
visit[smr] = true;
partDynamic(s1, visit, dyn, tree);
visit[smr] = false;
partDynamic(s2, visit, dyn, tree);
return dyn;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
auto n = load<int>();
auto s1 = load<int>() - 1;
auto s2 = load<int>() - 1;
auto tree = loadEdges(n, n-1);
auto root = researchRoots(s1, s2, n, tree);
auto answer = numeric_limits<int>::max();
for (auto i=0; i+1<(int)root.vertices.size(); ++i) {
auto dyn = brutCutDyn(s1, s2, root.vertices[i+1], n, tree, root);
answer = min(answer, max(dyn[s1].requirement, dyn[s2].requirement));
}
cout << answer << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
384 KB |
Output is correct |
| 2 |
Correct |
9 ms |
384 KB |
Output is correct |
| 3 |
Correct |
12 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2051 ms |
36728 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
