Submission #703423

#TimeUsernameProblemLanguageResultExecution timeMemory
703423406Mousetrap (CEOI17_mousetrap)C++17
100 / 100
1357 ms225196 KiB
#include "bits/stdc++.h" using namespace std; #define int long long const int N = 1e6 + 5; const long long INF = 1ll << 60; int F[N], n, T, M, ch[N], pr[N], bala[N]; vector<int> adj[N]; void dfs2(int v, int p) { for (auto u: adj[v]) if (u != p) { bala[u] = bala[v] + ch[v] - 1; dfs2(u, v); } } void dfs(int v, int p) { pr[v] = p; vector<int> tmp; for (auto u: adj[v]) if (u != p) { dfs(u, v); tmp.push_back(F[u]); ch[v]++; } sort(tmp.rbegin(), tmp.rend()); if (tmp.size() <= 1) F[v] = tmp.size(); else F[v] = tmp[1] + tmp.size(); } bool check(int O) { int m = M; int child = -1; int cur = 0; while (m != T) { int d = 0; for (auto u: adj[m]) if (u != pr[m] && u != child) { int x = F[u] + bala[u] + (m == M); if (x >= O) { cur--; d--; } } cur++; if (cur < 0) return false; O += d; child = m; m = pr[m]; } return O > 0; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> T >> M; T--, M--; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; u--, v--; adj[u].push_back(v); adj[v].push_back(u); } if (M == T) { cout << 0 << '\n'; return 0; } dfs(T, T); ch[T] = 1; dfs2(T, T); for (int i = 0; i < n; i++) { sort(adj[i].begin(), adj[i].end(), [&](const int x, const int y) {return F[x] + bala[x] > F[y] + bala[y];}); } int l = 0, r = INF; while (r - l > 1) { int m = l + r >> 1; if (check(m)) r = m; else l = m; } cout << l << '\n'; return 0; }

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:79:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |   int m = l + r >> 1;
      |           ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...