| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 857974 | Trisanu_Das | Village (BOI20_village) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> adj[100005];
ll posmin[100005], posmax[100005], sz[100005], dec1[100005], dec2[100005], ansmin = 0, ansmax = 0, n, cnt = 0;
vector<bool> vis;
void dfs(int u, int p){
sz[x] = 1;
for(auto v : adj[x]){
if(v == p)continue;
dfs(v, u);
sz[u] += sz[v];
if(vis[v]) continue;
vis[u] = true;
swap(posmin[u], posmin[v]);
ansmin += 2;
}
if(u) ansmax += min(sz[x], n - sz[x]) * 2;
else if(!vis[0]){
swap(posmin[0], posmin[adj[0][0]]);
ansmin += 2;
}
}
void findroot(int u, int p){
for(auto v : adj[u]){
if(v == p) continue;
if(sz[i] > (n >> 1)){
dec1[i] = 0;
dec2[0] = v;
findroot(v, x);
}
}
}
void encode(int u, int p){
dec1[cnt] = u;
dec2[u] = cnt++;
for(auto v : adj[x]){
if(v == p) continue;
encode(v, u);
}
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> n;
iota(posmin.begin(), posmin.end(), 0);
iota(posmax.begin(), posmax.end(), 0);
for(int i = 0; i < n-1; ++i){
int u, v; cin >> u >> v;
adj[u - 1].push_back(v - 1);
adj[v - 1].push_back(u - 1);
}
dfs(0, 0);
findroot(0, 0);
encode(dec1[0], dec1[0]);
for(int i = 0; i < n; i++) posmax[i] = dec1[(dec2[i] + n / 2)%n];
cout << ansmin << ' ' << ansmax << '\n';
for(auto x : posmin) cout << x + 1 << ' ';
cout << '\n';
for(auto x : posmax) cout << x + 1 << ' ';
cout << '\n';
}