| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1093131 | Jawad_Akbar_JJ | Village (BOI20_village) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
vector<int> nei[N], lst;
int Num[N], Num2[N], ch[N];
long long Mx = 0, Mn = 0, n;
void dfs(int u, int p, int c = 0){
ch[u] = 1;
for (int i : nei[u]){
if (i == p)
continue;
dfs(i, u, c);
ch[u] += ch[i];
Mx += min(n - ch[i], ch[i]);
}
if (c == 0)
return;
vector<int> vec = {u};
for (int i : nei[u]){
if (i == p)
continue;
if (Num2[i] == i or (u == 1 and vec.size() == 1)){
int k = Num2[i];
Num2[i] = vec.back();
vec.push_back(k);
}
}
Num2[u] = vec.back();
Mn += (vec.size() - 1) * 2;
}
int find_cent(int u, int p){
for (int i : nei[u])
if (i != p and ch[i] * 2 > ch[1])
return find_cent(i, u);
return u;
}
void get(int u, int p){
for (int i : nei[u])
if (i != p)
get(i, u);
lst.push_back(u);
}
vector<int> get(int a, int b, int c){
lst.clear();
get(a, b);
return lst;
}
void solve(){
dfs(1, 1, 1);
int rt = find_cent(1, 1), ind = 0;
dfs(rt, rt);
vector<pair<int,int>> vec;
for (int i : nei[rt])
vec.push_back({ch[i], i});
sort(rbegin(vec), rend(vec));
vector<int> Vec =get(vec[0].second, rt, 1);
for (int i=1;i<vec.size();i++){
vector<int> v = get(vec[i].second, rt, 1);
for (int j : v)
Num[j] = Vec[ind++], Vec.push_back(j);
}
Vec.push_back(rt);
Num[rt] = Vec[ind++];
get(vec[0].second, rt, 1);
for (int i : lst)
Num[i] = Vec[ind++];
}
int main(){
cin>>n;
for (int i=1, a, b;i<n;i++){
cin>>a>>b;
nei[a].push_back(b);
nei[b].push_back(a);
}
if (n == 1){
cout<<1 / 0;
return 0;
}
solve();
cout<<Mn<<" "<<Mx<<'\n';
for (int i=1;i<=n;i++)
cout<<Num2[i]<<' ';
cout<<'\n';
for (int i=1;i<=n;i++)
cout<<Num[i]<<' ';
cout<<'\n';
}