Submission #1017788

#TimeUsernameProblemLanguageResultExecution timeMemory
1017788VMaksimoski008Village (BOI20_village)C++17
100 / 100
46 ms15564 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() //#define int long long using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 1e5 + 5; int n; vector<int> graph[maxn]; ll mn=0, mx=0; vector<int> ansMn(maxn), ansMx(maxn), sub(maxn), euler; void dfs(int u, int p) { sub[u] = 1; euler.push_back(u); for(int &v : graph[u]) { if(v == p) continue; dfs(v, u); sub[u] += sub[v]; } mx += min(sub[u], n - sub[u]); if(u == ansMn[u]) { mn += 2; if(p) swap(ansMn[u], ansMn[p]); else swap(ansMn[u], ansMn[graph[u].back()]); } } signed main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); cin >> n; for(int i=1; i<=n; i++) ansMn[i] = ansMx[i] = i; for(int i=0; i<n-1; i++) { int a, b; cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); } dfs(1, 0); cout << mn << " " << 2 * mx << '\n'; for(int i=0; i<n; i++) ansMx[euler[i]] = euler[(i+n/2)%n]; for(int i=1; i<=n; i++) cout << ansMn[i] << " "; cout << '\n'; for(int i=1; i<=n; i++) cout << ansMx[i] << " "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...