Submission #161420

#TimeUsernameProblemLanguageResultExecution timeMemory
161420MinnakhmetovMousetrap (CEOI17_mousetrap)C++14
100 / 100
1319 ms219628 KiB
#include <bits/stdc++.h> #define ll long long #define all(aaa) aaa.begin(), aaa.end() using namespace std; const int N = 1e6 + 5, INF = 1e9; vector<int> g[N]; int n, m, t; bool term[N]; vector<vector<int>> w; void dive(int node, int anc) { if (node == t) term[node] = 1; for (int to : g[node]) { if (to != anc) { dive(to, node); if (term[to]) term[node] = 1; } } } int dfs(int node, int anc) { int adj = g[node].size() - (anc != -1); vector<int> v; for (int to : g[node]) { if (to != anc) { v.push_back(dfs(to, node) + 1); } } sort(v.rbegin(), v.rend()); if (v.empty()) return 0; else if (v.size() == 1) return 1; return v[1] + adj - 1; } int walk(int node, int anc) { if (node == t) return 0; vector<int> v; for (int to : g[node]) { if (to != anc && !term[to]) { v.push_back(dfs(to, node) + 1); } } int add = 0; for (int to : g[node]) { if (to != anc) { if (term[to]) { add = walk(to, node); } } } for (int &x : v) x += v.size() - 1 + add; sort(v.begin(), v.end()); w.push_back(v); add += v.size(); return add; } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cin >> n >> t >> m; m--, t--; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--, b--; g[a].push_back(b); g[b].push_back(a); } dive(m, -1); walk(m, -1); reverse(all(w)); // for (auto &v : w) { // for (int x : v) { // cout << x << " "; // } // cout << "\n"; // } int l = -1, r = INF; while (r - l > 1) { int p = (l + r) >> 1; bool ok = true; int energy = 0, expended = 0; for (auto &v : w) { energy++; for (int x : v) { if (x + expended > p) { if (energy == 0 || expended + 1 > p) { ok = false; break; } expended++; energy--; } } if (!ok) break; } if (ok) r = p; else l = p; } cout << r << "\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...