Submission #824738

#	Time	Username	Problem	Language	Result	Execution time	Memory
824738		tch1cherin	Village (BOI20_village)	C++17	56 / 100	105 ms	20144 KiB

Village

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

const int MAX_N = 1e5 + 5, MAX_L = __lg(MAX_N) + 1;
vector<int> G[MAX_N];
int up[MAX_L][MAX_N];
int depth[MAX_N];
vector<int> ord;

void DFS(int u, int p) {
  depth[u] = (u == 0 ? 0 : depth[p] + 1);
  ord.push_back(u);
  up[0][u] = p;
  for (int i = 1; i < MAX_L; i++) {
    up[i][u] = up[i - 1][up[i - 1][u]];
  }
  for (int v : G[u]) {
    if (v != p) {
      DFS(v, u);
    }
  }
}

int lca(int u, int v) {
  if (depth[u] < depth[v]) {
    swap(u, v);
  }
  for (int i = MAX_L - 1; i >= 0; i--) {
    if (depth[u] - depth[v] >= (1 << i)) {
      u = up[i][u];
    }
  }
  if (u == v) {
    return u;
  }
  for (int i = MAX_L - 1; i >= 0; i--) {
    if (up[i][u] != up[i][v]) {
      u = up[i][u];
      v = up[i][v];
    }
  }
  return up[0][u];
}

int distance(int u, int v) {
  return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N;
  cin >> N;
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  DFS(0, 0);
  int64_t smallest = 0, largest = 0;
  queue<int> leaves;
  vector<int> value(N), degree(N);
  iota(value.begin(), value.end(), 0);
  for (int i = 0; i < N; i++) {
    degree[i] = (int)G[i].size();
    if (degree[i] == 1) {
      leaves.push(i);
    }
  }
  vector<bool> deleted(N, false);
  while (!leaves.empty()) {
    int u = leaves.front();
    leaves.pop();
    deleted[u] = true;
    for (int v : G[u]) {
      if (!deleted[v]) {
        degree[v]--;
        if (degree[v] == 1) {
          if (value[u] == u) {
            smallest += 2;
            swap(value[u], value[v]);
          }
          leaves.push(v);
        }
      }
    }
    if (value[u] == u) {
      smallest += 2;
      swap(value[u], value[G[u][0]]);
    }
  }
  int64_t sum = 0;
  for (int i = 0; i < N; i++) {
    assert(value[i] != i);
    sum += distance(i, value[i]);
  }
  assert(sum == smallest);
  vector<int> large(N);
  for (int i = 0; i < N; i++) {
    largest += distance(ord[i], ord[(i + N / 2) % N]);
    large[ord[i]] = ord[(i + N / 2) % N];
  }
  cout << smallest << " " << largest << "\n";
  for (int i = 0; i < N; i++) {
    cout << 1 + value[i] << " \n"[i + 1 == N];
  }
  for (int i = 0; i < N; i++) {
    cout << 1 + large[i] << " \n"[i + 1 == N];
  }
}

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