Submission #824759

#	Time	Username	Problem	Language	Result	Execution time	Memory
824759		tch1cherin	Village (BOI20_village)	C++17	100 / 100	112 ms	20512 KiB

Village

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

const int MAX_N = 1e5 + 5;
const int MAX_L = __lg(MAX_N) + 1;
int up[MAX_L][MAX_N];
vector<int> G[MAX_N];
int depth[MAX_N], small[MAX_N], large[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 = 0; i < MAX_L - 1; i++) {
    up[i + 1][u] = up[i][up[i][u]];
  }
  for (int v : G[u]) {
    if (v != p) {
      DFS(v, u);
    }
  }
  if (small[u] == u) {
    swap(small[u], small[u == 0 ? G[u][0] : p]);
  }
}

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);
  }
  iota(small, small + N, 0);
  DFS(0, 0);
  for (int i = 0; i < N; i++) {
    large[ord[i]] = ord[(i + N / 2) % N];
  }
  int64_t smallest = 0, largest = 0;
  for (int i = 0; i < N; i++) {
    smallest += distance(i, small[i]);
    largest += distance(i, large[i]);
  }
  cout << smallest << " " << largest << "\n";
  for (int i = 0; i < N; i++) {
    cout << 1 + small[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: 38 / 38
• Subtask 3: 50 / 50