Submission #261662

#	Time	Username	Problem	Language	Result	Execution time	Memory
261662		rama_pang	Village (BOI20_village)	C++14	100 / 100	188 ms	26060 KiB

Village

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

const int MAXN = 1e5 + 5;

namespace minimum {

int N;
vector<int> adj[MAXN];
int ans[MAXN];
int dp[MAXN];
int score = 0;

void Dfs(int u, int p) {
  for (auto v : adj[u]) if (v != p) {
    Dfs(v, u);
    if (ans[v] == 0 && ans[u] == 0) {
      ans[u] = v;
      ans[v] = u;
      score += 2;
    } else if (ans[v] == 0) {
      ans[v] = ans[u];
      ans[u] = v;
      score += 2;
    }
  }

  if (ans[u] == 0 && p == 0) {
    int ch = ans[adj[u][0]];
    ans[u] = ch;
    ans[adj[u][0]] = u;
    score += 2;
  }
}

pair<long long, vector<int>> SolveMinimum(int N, vector<int> U, vector<int> V) {
  minimum::N = N;
  for (int i = 0; i + 1 < N; i++) {
    int u = U[i], v = V[i];
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  Dfs(1, 0);
  
  vector<int> res;
  for (int i = 1; i <= N; i++) {
    assert(ans[i] != i);
    res.emplace_back(ans[i]);
  }
  return {score, res};
}

} /// namespace minimum

namespace maximum {

int N;
vector<int> adj[MAXN];

int ans[MAXN];
int identity[MAXN];
long long score = 0;

int sz[MAXN];
int par[MAXN];

void Calc(int u, int p) {
  sz[u] = 1;
  for (auto v : adj[u]) if (v != p) {
    Calc(v, u);
    sz[u] += sz[v];
    score += 2 * min(sz[v], N - sz[v]);
  }
}

void Dfs(int u, int p) {
  par[u] = p, sz[u] = 1;
  for (auto v : adj[u]) if (v != p) {
    Dfs(v, u);
    sz[u] += sz[v];
  }
}

int Centroid(int u) {
  Dfs(u, 0);
  int total_sz = sz[u];
  while (true) {
    pair<int, int> mx = {-1, -1};
    for (auto v : adj[u]) if (v != par[u]) {
      mx = max(mx, {sz[v], v});
    }
    if (mx.first * 2 <= total_sz) {
      return u;
    }
    u = mx.second;
  }
  return -1;
}

void GetNodes(int u, int p, vector<int> &nodes) {
  nodes.emplace_back(u);
  for (auto v : adj[u]) if (v != p) {
    GetNodes(v, u, nodes);
  }
}

void Solve() {
  int u = Centroid(1);
  Dfs(u, 0);
  vector<int> nodes = {u};
  pair<int, int> mx = {1, u};
  for (auto v : adj[u]) {
    mx = max(mx, {sz[v], v});
    GetNodes(v, u, nodes);
  }
  vector<int> old_id(nodes.size());
  for (int i = 0; i < (int) nodes.size(); i++) {
    old_id[i] = identity[nodes[i]];
  }
  for (int i = 0; i < (int) nodes.size(); i++) {
    identity[nodes[i]] = old_id[(i - mx.first + (int) nodes.size()) % nodes.size()];
  }
}

pair<long long, vector<int>> SolveMaximum(int N, vector<int> U, vector<int> V) {
  maximum::N = N;
  iota(identity + 1, identity + N + 1, 1);
  for (int i = 0; i + 1 < N; i++) {
    int u = U[i], v = V[i];
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  Calc(1, 0);
  Solve();
  for (int i = 1; i <= N; i++) {
    ans[identity[i]] = i;
  }

  vector<int> res;
  for (int i = 1; i <= N; i++) {
    assert(ans[i] != i);
    res.emplace_back(ans[i]);
  }
  return {score, res};
}

} /// namespace maximum

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N;
  cin >> N;
  vector<int> U(N - 1), V(N - 1);
  for (int i = 0; i + 1 < N; i++) {
    cin >> U[i] >> V[i];
  }

  long long score_min, score_max;
  vector<int> ans_min, ans_max;
  tie(score_min, ans_min) = minimum::SolveMinimum(N, U, V);
  tie(score_max, ans_max) = maximum::SolveMaximum(N, U, V);
  
  cout << score_min << " " << score_max << "\n";
  for (int i = 0; i < N; i++) {
    cout << ans_min[i] << " \n"[i + 1 == N];
  }
  for (int i = 0; i < N; i++) {
    cout << ans_max[i] << " \n"[i + 1 == N];
  }
  return 0;
}

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