Submission #610538

#TimeUsernameProblemLanguageResultExecution timeMemory
610538ArnchMousetrap (CEOI17_mousetrap)C++17
25 / 100
899 ms79684 KiB
// oooo /* har chi delet mikhad bebar ~ gitar o ba khodet nabar! ~ ;Amoo_Hasan; */ #include<bits/stdc++.h> //#pragma GCC optimize("O3,no-stack-protector,unroll-loops") //#pragma GCC target("avx2,fma") using namespace std; typedef long long ll; typedef long double ld; #define Sz(x) int((x).size()) #define All(x) (x).begin(), (x).end() #define wtf(x) cout<<#x <<" : " <<x <<endl constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969; int n, t, m; bool mark[N]; ll dp[N], par[N], ps[N]; vector<int> adj[N]; void dfs(int x, int p = 0) { par[x] = p; int tim = 0; vector<ll> vc; for(auto j : adj[x]) { if(j == p) continue; tim++; dfs(j, x); vc.push_back(dp[j]); } sort(All(vc), greater<int>()); if(x != t) { ps[x] = ps[p] + tim - 1; } if(tim == 0) { dp[x] = 0; return; } if(tim == 1) { dp[x] = 1; return; } dp[x] = tim; dp[x] += vc[1]; } ll solve(int x) { vector<ll> vc; for(auto j : adj[x]) { if(mark[j] || j == par[x]) continue; vc.push_back(dp[j]); } sort(All(vc), greater<int>()); ll cnt = ps[par[x]]; cnt += Sz(vc); if(Sz(vc) >= 2) cnt += vc[1]; return cnt; } int main() { ios :: sync_with_stdio(0), cin.tie(0); cin >>n >>t >>m; for(int i = 0; i < n - 1; i++) { int u, v; cin >>u >>v; adj[u].push_back(v), adj[v].push_back(u); } dfs(t); ll ans = solve(m); mark[m] = 1; int x = par[m]; while(x != t) { ans = max(ans, solve(x)); mark[x] = 1; x = par[x]; } cout<<ans; 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...