Submission #1051999

#TimeUsernameProblemLanguageResultExecution timeMemory
1051999duckindogVillage (BOI20_village)C++17
6 / 100
1102 ms12156 KiB
#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], rvs[N], it; int f[N][17], lg[N]; void dfs0(int u, int p = -1) { sz[u] = 1; st[u] = ++it; rvs[it] = u; for (const auto& v : ad[u]) { if (v == p) continue; d[v] = d[u] + 1; dfs0(v, u); ed[u] = ++it; rvs[it] = u; sz[u] += sz[v]; length += 2 * min(sz[v], n - sz[v]); } } void init() { for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1; for (int i = 1; i <= it; ++i) f[i][0] = rvs[i]; 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); do { 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; } while (next_permutation(answer.begin(), answer.end())); } } 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:128:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  128 |         auto lt = f[i][j - 1], rt = f[i + (1 << j - 1)][j - 1];
      |                                                 ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...