Submission #971998

#TimeUsernameProblemLanguageResultExecution timeMemory
971998jadai007Village (BOI20_village)C++17
100 / 100
52 ms18628 KiB
#include<bits/stdc++.h> #define int long long using namespace std; int n, dp[100100], vln[100100], vlx[100100], ansn, ansx, cen, depth[100100]; vector<int> vc[100100], ans; void dfs(int u, int pa){ for(auto v:vc[u]){ if(v == pa) continue; dfs(v, u); if(vln[v] == v){ ansn+=2; swap(vln[v], vln[u]); } dp[u]+=dp[v]; } } void dfs2(int u, int pa){ ans.emplace_back(u); for(auto v:vc[u]){ if(v == pa) continue; depth[v] = depth[u] + 1; dfs2(v, u); } } int centroid(int u, int pa){ for(auto v:vc[u]){ if(v == pa) continue; if(dp[v] > n / 2) return centroid(v, u); } return u; } int32_t main(){ cin.tie(nullptr)->sync_with_stdio(false); cin >> n; for(int i = 1; i<=n; ++i) vln[i] = i; for(int i = 1; i<=n; ++i) dp[i] = 1; for(int i = 1; i<n; ++i){ int a, b; cin >> a >> b; vc[a].push_back(b); vc[b].push_back(a); } dfs(1, -1); if(vln[1] == 1){ ansn+=2; swap(vln[1], vln[vc[1][0]]); } cen = centroid(1, -1); dfs2(cen, -1); for(int i = 1; i<=n; ++i) ansx+=depth[i]*2; cout << ansn << ' ' << ansx << '\n'; for(int i = 0; i<n; ++i) vlx[ans[(i+n/2)%n]] = ans[i]; for(int i = 1; i<=n; ++i) cout << vln[i] << ' '; cout << '\n'; for(int i = 1; i<=n; ++i) cout << vlx[i] << ' '; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...