Submission #1050893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050893		duckindog	Village (BOI20_village)	C++17	0 / 100	2 ms	9292 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> 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 = 1;
    answer = vector<int>(n, 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: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50