Submission #1051852

#TimeUsernameProblemLanguageResultExecution timeMemory
1051852duckindogVillage (BOI20_village)C++17
50 / 100
82 ms41144 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 sz[N], st[N], it; void dfs0(int u, int p = -1) { st[u] = ++it; sz[u] = 1; for (const auto& v : ad[u]) { if (v == p) continue; dfs0(v, u); sz[u] += sz[v]; length += 2 * min(sz[v], n - sz[v]); } } vector<int> answer; void solve() { dfs0(1); vector<pair<int, int>> vt; for (int i = 1; i <= n; ++i) vt.push_back({i, i}); sort(vt.begin(), vt.end(), [&](const auto& a, const auto& b) { return st[a.first] < st[b.first]; }); for (int i = 1; i <= n; ++i) swap(vt[i - 1].first, vt[(i + n / 2 - 1) % n].first); answer.resize(n); for (const auto& x : vt) answer[x.second - 1] = x.first; } } 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]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...