Submission #610521

#TimeUsernameProblemLanguageResultExecution timeMemory
610521ArnchMousetrap (CEOI17_mousetrap)C++17
25 / 100
764 ms64088 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; bool flag = false, mark[N]; int dp[N], par[N]; vector<int> adj[N]; void dfs(int x, int p = 0) { par[x] = p; int tim = 0; vector<int> 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(tim == 0) { dp[x] = 0; return; } if(tim == 1) { dp[x] = 1; return; } dp[x] = tim; dp[x] += vc[1]; } int main() { ios :: sync_with_stdio(0), cin.tie(0); int n, t, m; 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); if(u == t && v == m) flag = true; if(u == m && v == t) flag = true; } dfs(t); int ans = dp[m]; mark[m] = 1; int x = par[m]; while(x != 0) { vector<int> vc; for(auto j : adj[x]) { if(mark[j] || j == par[x]) continue; vc.push_back(dp[j]); } sort(All(vc), greater<int>()); ans += Sz(vc); if(Sz(vc) >= 2) ans += vc[1]; 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...