Submission #618098

#TimeUsernameProblemLanguageResultExecution timeMemory
618098narvaloUntitled (POI11_ins)C++17
100 / 100
1303 ms131072 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; if (n == 1) { cout << 0 << '\n'; return 0; } vector<vector<int>> adj(n); for (int i = 0 ; i < n - 1 ; i += 1) { int a , b; cin >> a >> b; a -= 1 , b -= 1; adj[a].push_back(b); adj[b].push_back(a); } vector<pair<int , int>> dp(n); function<pair<int , int>(int , int)> Dfs = [&](int node , int pre) { int ans = 1; for (auto x : adj[node]) { if (x == pre) continue; ans += Dfs(x , node).first; } return dp[node] = make_pair(ans , pre); }; Dfs(0 , -1); long long ans = 0; int max_depth = 0; function<void(int , int , int , int , bool)> Get = [&](int node , int pre , int depth , int sub , bool now) { if (now) { max_depth = max(depth , max_depth); } ans += 1LL * depth * 2; for (auto x : adj[node]) { if (x == pre) continue; bool c1 = (x == sub || sub == -1); Get(x , node , depth + 1 , sub , now | c1); } return ; }; auto Init = [&]() { max_depth = 0; ans = 0; return ; }; vector<int> sum(n); for (int i = 0 ; i < n ; i++) { for (auto x : adj[i]) { if (x == dp[i].second) continue; sum[i] += dp[x].first; } } for (int node = 0 ; node < n ; node += 1) { vector<pair<int , int>> comps; int id = 0 , cnt = 0; for (auto x : adj[node]) { int sz = (x == dp[node].second ? n - 1 - sum[node] : dp[x].first); comps.emplace_back(sz , x); if (comps[id].first <= sz) { id = cnt; } cnt += 1; } int mx = comps[id].first; int sub = comps[id].second; if (mx > n - mx) { cout << -1 << '\n'; continue; } else { if (n - 2 * mx == 0) { Get(node , -1 , 0 , sub , 0); } else { Get(node , -1 , 0 , -1 , 0); } cout << ans - max_depth << '\n'; Init(); } } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...