Submission #1052371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052371		duckindog	Village (BOI20_village)	C++17	100 / 100	76 ms	42676 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 sz[N], st[N], rvs[N], it;
  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;
      dfs0(v, u);
      sz[u] += sz[v];
      length += 2 * min(sz[v], n - sz[v]);
    }
  }
 
  vector<int> answer;
  void solve() { 
    dfs0(1);
    vector<int> vt(n); iota(vt.begin(), vt.end(), 1);
    sort(vt.begin(), vt.end(), [&](const auto& a, const auto& b) { 
      return st[a] < st[b];
    });
    vt.insert(vt.end(), vt.begin(), vt.begin() + (n + 1) / 2);
    vt.erase(vt.begin(), vt.begin() + (n + 1) / 2);

    answer.resize(n);
    for (int i = 1; i <= n; ++i) answer[rvs[i] - 1] = vt[i - 1];
  }
}
 
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];
}

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