Submission #705589

#TimeUsernameProblemLanguageResultExecution timeMemory
705589KahouMousetrap (CEOI17_mousetrap)C++14
0 / 100
5069 ms66032 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define endl '\n' #define mk make_pair typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int N = 1e6 + 50; ll n, t, m, val[N], dp[N], ps[N], k; bool mark[N]; vector<int> adj[N]; vector<int> vp; vector<pii> vc; void dfs(int u, int p=0) { if (u == t) return; int mx1 = 0, mx2 = 0; for (int v:adj[u]) { if (v == p) continue; dfs(v, u); if (mark[v]) { mark[u] = 1; val[u] = val[v] + adj[u].size()-1-(p>0); } else { if (dp[v] > mx1) { mx2 = mx1; mx1 = dp[v]; } else if (dp[v] > mx2) { mx2 = dp[v]; } } } if (!mark[u]) { dp[u] = adj[u].size()-(p>0) + mx2; } else { vp.push_back(u); for (int v:adj[u]) { if (v == p) continue; if (mark[v]) continue; vc.push_back({u, dp[v] + val[u]}); } } } bool isval(ll x) { int prv = 0; int tmp = 0; for (pii p:vc) { if (p.F != prv) { ps[p.F] = ps[prv]; tmp = ps[prv]; prv = p.F; } if (tmp+p.S > x) { ps[p.F]++; } if (ps[p.F] > min(1ll*p.F, x)) return 0; } return 1; } void solve() { cin >> n >> t >> m; for (int i = 1; i <= n-1; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } mark[t] = 1; dfs(m); reverse(vp.begin(), vp.end()); reverse(vc.begin(), vc.end()); for (pii &x : vc) { if (x.F != vp[k]) k++; x.F = k+1; } k = vp.size(); ll dw = -1, up = 1e18; while (up-dw > 1) { int md = (up+dw)>>1; if (isval(md)) up = md; else dw = md; } cout << up << endl; } int main() { ios::sync_with_stdio(0), cin.tie(0); solve(); 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...