Submission #1050891

#TimeUsernameProblemLanguageResultExecution timeMemory
1050891duckindogVillage (BOI20_village)C++17
0 / 100
1 ms9308 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> vt; for (const auto& v : ad[u]) { if (v == p) continue; dfs0(v, u); vt.push_back(v); } if (vt.size()) { sort(vt.begin(), vt.end(), [&](const auto& a, const auto& b) { return f[a][1] - f[a][0] > f[b][1] - f[b][0]; }); auto transition = [&](long long& ret, auto& trace, vector<int> vt) { while (vt.size() > 1) { int value = f[vt.back()][1] + f[vt.end()[-2]][1] + 4; if (value <= f[vt.back()][0] + f[vt.end()[-2]][0]) { ret = min(MAX, ret + value); trace.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]); trace.emplace_back(1, x, 0); } }; transition(f[u][1], trace[u][1], vt); f[u][0] = f[vt.back()][1] + 2; trace[u][0].emplace_back(2, vt.back(), 1); transition(f[u][0], trace[u][0], vector<int>(vt.begin(), vt.end() - 1)); if (f[u][0] > f[u][1] + 2) { f[u][0] = f[u][1] + 2; trace[u][0] = {make_tuple(3, vt.back(), 0)}; } } if (f[u][1] >= MAX) f[u][1] = 2 * MAX; if (f[u][0] >= MAX) 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, 1); 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 { int length; vector<int> answer; void solve() { length = 0; answer.resize(n); } } 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...