Submission #1033048

#TimeUsernameProblemLanguageResultExecution timeMemory
1033048vjudge1Village (BOI20_village)C++17
100 / 100
47 ms23744 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ll long long #define ar array #define ld long double const int N = 3e5 + 20; const int K = 200; const int INF = 1e15; const int LOG = 24; const int MOD = 998244353; vector<int> g[N], ord; int n, posLo[N], posHi[N], ansLo, ansHi, sz[N]; void dfs(int x,int p){ //cout<<x<<endl; sz[x] = 1; ord.push_back(x); for(auto u: g[x]){ if(u == p)continue; dfs(u, x); sz[x] += sz[u]; ansHi += min(sz[u], n - sz[u]); } if(posLo[x] == x){ if(p == -1)swap(posLo[x], posLo[g[x][0]]); else swap(posLo[x], posLo[p]); ansLo += 2; } } signed main(){ios_base::sync_with_stdio(false);cin.tie(0); cin>>n; for(int i = 1;i < n;i++){ int u, v; cin>>u>>v; --u, --v; g[u].push_back(v); g[v].push_back(u); } for(int i = 0;i < n;i++)posLo[i] = i; dfs(0, -1); ansHi *= 2; for(int i = 0;i < n;i++){ //cout<<i<<endl; int u = ord[i]; int v = ord[(i + n / 2 ) % n]; posHi[u] = v; } //assert(0); cout<<ansLo<<" "<<ansHi<<'\n'; for(int i = 0;i < n;i++)cout<<posLo[i] + 1<<" "; cout<<'\n'; for(int i = 0;i < n;i++)cout<<posHi[i] + 1<<" "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...