Submission #250338

#TimeUsernameProblemLanguageResultExecution timeMemory
250338SortingMousetrap (CEOI17_mousetrap)C++14
100 / 100
1208 ms160888 KiB
#include <bits/stdc++.h> using namespace std; const int k_N = 1e6 + 3; int n, trap, mouse; int a[k_N], d[k_N], dp[k_N]; vector<int> adj[k_N]; vector<pair<int, int>> v; void dfs(int u, int p){ pair<int, int> ret; for(int to: adj[u]){ if(to == p) continue; if(p != -1) dp[to] += dp[u] + adj[u].size() - 2; dfs(to, u); a[u] |= a[to]; ret.second = max(dp[to], ret.second); if(ret.second > ret.first) swap(ret.first, ret.second); } if(adj[u].size() > 2) dp[u] = ret.second; dp[u] += adj[u].size() > 1; } void dfs2(int u, int p){ if(u == trap) return; for(int to: adj[u]){ if(to == p) continue; d[to] = d[u] + 1; dfs2(to, u); if(a[u] && !a[to]) v.push_back({d[to], dp[to] + (u == mouse)}); } } bool works(int x){ int ret = 0; for(auto p: v){ if(ret > p.first) return false; ret += (p.second + ret) > x; } return ret <= x; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> trap >> mouse; for(int i = 0; i < n - 1; ++i){ int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } a[mouse] = 1; d[mouse] = -1; dfs(trap, -1); dfs2(mouse, -1); sort(v.begin(), v.end()); int l = 0, r = n; while(l != r){ int mid = (l + r) >> 1; if(works(mid)) r = mid; else l = mid + 1; } cout << r << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...