Submission #971389

#	Time	Username	Problem	Language	Result	Execution time	Memory
971389		maxFedorchuk	Village (BOI20_village)	C++17	100 / 100	74 ms	22304 KiB

Village

#include <bits/stdc++.h> ///sadkj;;basdbfalsdfhblkabsjfbasdkjfbksabfkdsjbfalkbflkablksdbfkjablkfbaslkfdb
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=200005;
const int INF=1e18;
int n,mn=0,mx=0,total=0;
vector<int> adj[N],v(N),v1(N),sz(N,1);
vector<int> rec;
void dfs(int k,int pa){
  for(int j:adj[k]){
    if(j==pa)continue;
    dfs(j,k);
    if(v[j]==j){
      swap(v[j],v[k]);
      mn+=2;
    }
    sz[k]+=sz[j];
  }
}
int cen(int k,int pa){
  for(int j:adj[k]){
    if(j==pa)continue;
    if(sz[j]>n/2){
      return cen(j,k);
    }
  }
  return k;
}
void dfs1(int k,int pa,int deep){
  total+=deep*2;
  rec.push_back(k);
  for(int j:adj[k]){
    if(j==pa)continue;
    dfs1(j,k,deep+1);
  }
}
int32_t main() {
  LCBorz;
  cin>>n;
  for(int i=1;i<n;i++){
    int a,b;cin>>a>>b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  iota(all(v),0);
  dfs(1,1);
  if(v[1]==1){
    swap(v[1],v[adj[1][0]]);
    mn+=2;
  }
  int c=cen(1,1);
  dfs1(c,c,0);
  mx=total;
  for(int i=0;i<n;i++){
    v1[rec[(i+n/2)%n]]=rec[i];
  }
  cout<<mn<<' '<<mx<<endl;
  for(int i=1;i<=n;i++){
    cout<<v[i]<<' ';
  }
  cout<<endl;
  for(int i=1;i<=n;i++){
    cout<<v1[i]<<' ';
  }
  cout<<endl;
  return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 38 / 38
• Subtask 3: 50 / 50