Submission #1276012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276012		julia_08	Village (BOI20_village)	C++20	0 / 100	2 ms	12092 KiB

Village

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 1e5 + 10;

int to[MAXN];

int sub[MAXN], used[MAXN];

vector<int> adj[MAXN];

int get_size(int v, int p){

  sub[v] = 1;

  for(auto u : adj[v]){
    if(used[u] || u == p) continue;
    sub[v] += get_size(u, v);
  }

  return sub[v];

}

int get_centroid(int v, int p, int sz){

  for(auto u : adj[v]){
    if(used[u] || u == p) continue;
    if(sub[u] > sz / 2) return get_centroid(u, v, sz); 
  }

  return v;

}

void get_vtx(int v, int p, vector<int> &vtx){

  if(v != p) vtx.push_back(v);

  for(auto u : adj[v]){
    if(used[u] || u == p) continue;
    get_vtx(u, v, vtx);
  }

}

ll ans = 0;

void build(int v, int p){

  int c = get_centroid(v, p, get_size(v, p));

  used[c] = 1;

  vector<pair<int, int>> to_add;

  for(auto u : adj[c]){
    if(used[u]) continue;
    to_add.push_back({sub[u], u});
  }

  sort(to_add.begin(), to_add.end());

  vector<int> vtx;

  for(auto [s, u] : to_add) get_vtx(u, c, vtx);

  int sz = (int) vtx.size();

  ans += 2 * sz;

  if(sz % 2 == 1){

    for(int i=1; i<((sz + 1) / 2); i++) swap(to[vtx[i]], to[vtx[sz - i]]);

    swap(to[vtx[0]], to[c]);

  } else if(sz > 0){

    for(int i=1; i<(sz / 2); i++) swap(to[vtx[i]], to[vtx[sz - 1 - i]]);

    int x = to[vtx[0]], y = to[c], z = to[vtx[sz - 1]];

    to[vtx[sz - 1]] = x;
    to[vtx[0]] = y;
    to[c] = z;

  }

  for(auto u : adj[c]){
    if(used[u]) continue;
    build(u, c);
  }

}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);

  int n; 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);

  }

  for(int i=1; i<=n; i++) to[i] = i;

  build(1, 1);

  cout << "1 " << ans << "\n";

  for(int i=1; i<=n; i++) cout << "1 ";

  cout << "\n";

  for(int i=1; i<=n; i++){
    assert(to[i] != i);
    cout << to[i] << " ";
  }

  cout << "\n";

  return 0;
}

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