Submission #1052042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052042		duckindog	Village (BOI20_village)	C++17	31 / 100	703 ms	48976 KiB

Village

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
const long long MAX = 1'000'000'000'000'000'000;
int n;
vector<int> ad[N];

namespace findMin { 
  long long f[N][2];
  vector<tuple<int, int, int>> trace[N][2];
  void dfs0(int u, int p = -1) { 
    f[u][1] = 0;
    
    vector<int> best;
    for (const auto& v : ad[u]) { 
      if (v == p) continue;
      dfs0(v, u);
      best.push_back(v);
    }

    if (best.size()) { 
      sort(best.begin(), best.end(), [&](const auto& a, const auto& b) { 
        return f[a][1] - f[a][0] > f[b][1] - f[b][0];
      });

      { //f[u][1]
        vector<int> vt = best;
        auto& ret = f[u][1];
        auto& tr = trace[u][1];

        while (vt.size() > 1) { 
          long long value = min(MAX, f[vt.back()][1] + f[vt.end()[-2]][1] + 4);  
          if (value <= min(MAX, f[vt.back()][0] + f[vt.end()[-2]][0])) { 
            ret = min(MAX, ret + value);
            tr.emplace_back(0, vt.back(), vt.end()[-2]);
            vt.pop_back();
            vt.pop_back();
          } else break;
        }
        for (const auto& x : vt) {
          ret = min(MAX, ret + f[x][0]);
          tr.emplace_back(1, x, 0);
        }
      }
      
      { //f[u][0]
        vector<int> vt = best;
        auto& ret = f[u][0];
        auto& tr = trace[u][0];

        ret = f[vt.back()][1] + 2;
        tr.emplace_back(2, vt.back(), 1);
        vt.pop_back();
        for (const auto& x : vt) { 
          if (f[x][1] + 2 <= f[x][0]) { 
            ret = min(MAX, ret + f[x][1] + 2);
            tr.emplace_back(2, x, 1);
          } else { 
            ret = min(MAX, ret + f[x][0]);
            tr.emplace_back(2, x, 0);
          }
        }
      }
      

      if (f[u][0] > f[u][1] + 2) { 
        f[u][0] = min(MAX, f[u][1] + 2);
        trace[u][0] = {make_tuple(3, best.back(), 0)};
      }
    }
    if (f[u][1] >= MAX || f[u][1] < 0) f[u][1] = 2 * MAX;
    if (f[u][0] >= MAX || f[u][0] < 0) f[u][0] = MAX;
  }

  int vt[N];
  void dfs1(int u, int st) { 
    for (const auto& [type, a, b] : trace[u][st]) { 
      if (!type) { 
        dfs1(a, 1); dfs1(b, 1);
        swap(vt[a], vt[b]);
      } else if (type == 1) {
        dfs1(a, 0);
      } else if (type == 2) { 
        dfs1(a, b);
        if (b) swap(vt[u], vt[a]);
      } else { 
        dfs1(u, 1);
        swap(vt[u], vt[a]);
      }
    }
  }
  int length;
  vector<int> answer;
  void solve() { 
    memset(f, 14, sizeof f);
    dfs0(1);
    iota(vt + 1, vt + n + 1, 1);
    dfs1(1, 0);
    length = f[1][0];
    answer = vector<int>(vt + 1, vt + n + 1);
  }
}

namespace findMax { 
  long long length;
  int d[N], sz[N];
  int st[N], ed[N], it;
  int f[N][17], lg[N];
  void dfs0(int u, int p = -1) { 
    sz[u] = 1;
    st[u] = ++it; f[it][0] = u;
    for (const auto& v : ad[u]) { 
      if (v == p) continue;
      d[v] = d[u] + 1;
      dfs0(v, u);
      ed[u] = ++it; f[it][0] = u;
      sz[u] += sz[v];
      length += 2 * min(sz[v], n - sz[v]);
    }
  }
  void init() { 
    for (int i = 2; i <= it; ++i) lg[i] = lg[i >> 1] + 1;
    for (int j = 1; j <= 16; ++j) { 
      for (int i = 1; i + (1 << j) - 1 <= it; ++i) { 
        auto lt = f[i][j - 1], rt = f[i + (1 << j - 1)][j - 1];
        f[i][j] = (d[lt] <= d[rt] ? lt : rt);
      }
    }
  }
  int lca(int u, int v) { 
    int l = min(st[u], st[v]), r = max(st[u], st[v]);
    int j = lg[r - l + 1];
    auto lt = f[l][j], rt = f[r - (1 << j) + 1][j];
    return d[lt] <= d[rt] ? lt : rt;
  }
  int dis(int u, int v) { return d[u] + d[v] - 2 * d[lca(u, v)]; }

  vector<int> answer;
  void solve() { 
    dfs0(1);
    init();

    answer.resize(n); iota(answer.begin(), answer.end(), 1);
    mt19937 rng(137525724);
    for (;;) {
      shuffle(answer.begin(), answer.end(), rng);
      if (1.0 * clock() / CLOCKS_PER_SEC >= 0.68) break;
      int ret = 0;
      for (int i = 1; i <= n; ++i) {
        if (answer[i - 1] == i) { ret = -1; break; }
        ret += dis(answer[i - 1], i);
      }
      if (ret == length) break;
    }
  }
}

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

  cin >> n;
  for (int i = 1; i < n; ++i) { 
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
  }

  findMin::solve();
  findMax::solve();

  cout << findMin::length << " " << findMax::length << "\n";
  for (int i = 0; i < n; ++i) cout << findMin::answer[i] << " \n"[i == n - 1];
  for (int i = 0; i < n; ++i) cout << findMax::answer[i] << " \n"[i == n - 1];
}

Compilation message (stderr)

Village.cpp: In function 'void findMax::init()':
Village.cpp:127:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  127 |         auto lt = f[i][j - 1], rt = f[i + (1 << j - 1)][j - 1];
      |                                                 ~~^~~

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