Submission #434660

#TimeUsernameProblemLanguageResultExecution timeMemory
434660KoDMousetrap (CEOI17_mousetrap)C++17
25 / 100
1178 ms73340 KiB
#include <bits/stdc++.h> template <class T> using Vec = std::vector<T>; template <class F> struct RecLambda : private F { explicit RecLambda(F&& f) : F(std::forward<F>(f)) {} template <class... Args> decltype(auto) operator() (Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int N, T, M; std::cin >> N >> T >> M; T -= 1; M -= 1; Vec<Vec<int>> graph(N); for (int i = 0; i < N - 1; ++i) { int a, b; std::cin >> a >> b; a -= 1; b -= 1; graph[a].push_back(b); graph[b].push_back(a); } Vec<int> parent(N, -1); RecLambda([&](auto&& dfs, const int u) -> void { for (const int v : graph[u]) { if (parent[u] != v) { parent[v] = u; dfs(v); } } })(T); int ans = RecLambda([&](auto&& dfs, const int u) -> int { Vec<int> cand; for (const int v : graph[u]) { if (v != parent[u]) { cand.push_back(dfs(v)); } } std::sort(cand.rbegin(), cand.rend()); if (cand.size() <= 1) { return cand.size(); } return cand[1] + cand.size(); })(M); while (M != T) { ans += 1; M = parent[M]; } std::cout << ans - 1 << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...