Submission #669665

#TimeUsernameProblemLanguageResultExecution timeMemory
669665ziduoMousetrap (CEOI17_mousetrap)C++14
100 / 100
999 ms217292 KiB
/****************************************************************************** Online C++ Compiler. Code, Compile, Run and Debug C++ program online. Write your code in this editor and press "Run" button to compile and execute it. *******************************************************************************/ #include <bits/stdc++.h> using namespace std; const int INF = INT32_MAX; int N, T, M, P[1000005], rem[1000005]; int DP[1000005], deg[1000005], S[1000005]; vector<int> adj[1000005], C[1000005]; void dfs(int v, int p) { if(v == M) rem[v] = 1; for(auto u : adj[v]) { if(u == p) continue; dfs(u, v); P[u] = v; if(rem[u]) rem[v] = 1; else { C[v].push_back(u); ++deg[v]; } } sort(C[v].begin(), C[v].end(), [](int A, int B) { return DP[A] > DP[B]; }); if(C[v].size() <= 1) DP[v] = deg[v]; else DP[v] = deg[v] + DP[C[v][1]]; } void dfs(int v) { DP[v] += S[v]; for(auto u : adj[v]) { if(u == P[v]) continue; S[u] = S[v] + deg[v]; dfs(u); } } bool possible(int v) { int cur = 0, dep = 0; for(int e = M; e != T; e = P[e]) { ++dep; int k = 0; for(auto u : C[e]) { if(DP[u] + cur - k > v) ++cur, ++k; } if(cur > dep || cur > v) return false; } return true; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> T >> M; for(int l = 0; l < N - 1; l++) { int U, V; cin >> U >> V; adj[U].push_back(V); adj[V].push_back(U); } dfs(T, T); deg[T] = 0; dfs(T); int lo = 0, hi = N, ans = -1; while(lo <= hi) { int md = (lo + hi) / 2; if(possible(md)) ans = md, hi = md - 1; else lo = md + 1; } cout << ans << "\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...