API tools faq
paste
Advertisement
prog3r

brute best parts (2^(n-1))

prog3r
Jun 28th, 2025
374
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.47 KB | None | 0 0
raw download clone embed print report
  1. //#include "testlib.h"
  2. #include <bits/extc++.h>
  3. using namespace std;
  4. using namespace __gnu_pbds;
  5. template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  6. #define int long long
  7. #define YES(x) cout << (x?"YES\n":"NO\n")
  8. #define NO(x) cout << (x?"NO\n":"YES\n")
  9. #ifdef LO
  10. #pragma GCC optimize("trapv")
  11. #endif
  12. #ifndef LO
  13. #pragma GCC optimize("Ofast,unroll-loops")
  14. #endif
  15. //constexpr int MOD = (119<<23)+1;
  16. //constexpr int MOD = 967276608647009887ll;
  17. //constexpr int MOD = 1e9+7;
  18. constexpr int INF = 1e18;
  19. signed main() {
  20. #ifndef LO
  21.     clog << "FIO\n";
  22.     ios::sync_with_stdio(0);
  23.     cin.tie(0);
  24. #endif
  25.     cout << unitbuf;
  26. //#ifdef LO
  27. //    cout << unitbuf;
  28. //#endif
  29.     int n=22;
  30.     auto go = [&] () -> void {
  31.         vector<vector<int>> adj(n);
  32.         vector<pair<int,int>> edges;
  33.         for (int i = 1; i < n; i += 1) {
  34. //            int u = i, v = gen[i];
  35.             int u, v;
  36.             cin >> u >> v;
  37.             u -= 1, v -= 1;
  38.             edges.push_back({v, u});
  39.             adj[v].push_back(u);
  40.             adj[u].push_back(v);
  41.         }
  42.         int mini = INF;
  43.         int mini_i = -1;
  44.         int mini_rt = -1;
  45.         for (int i = 0; i < (1<<(n-1)); i += 1) {
  46.             for (int rt = 0; rt == 0; rt += 1) {
  47.                 vector<bool> heavy(n-1);
  48.                 vector<vector<pair<bool,int>>> wadj(n);
  49.                 for (int j = 0; j < n-1; j += 1) {
  50.                     wadj[edges[j].first].push_back({bool((1<<j)&i), edges[j].second});
  51.                     wadj[edges[j].second].push_back({bool((1<<j)&i), edges[j].first});
  52.                 }
  53.                 vector<int> head(n, -INF), end(n, -INF);
  54.                 vector<int> par(n, -INF);
  55.                 vector<int> d(n, -INF);
  56.                 auto dfs = [&] (auto f, int u, int hd) -> void {
  57.                     if (hd == -1) {
  58.                         hd = u;
  59.                         head[u] = u;
  60.                     }
  61.                     end[u] = u;
  62.                     bool leaf = true;
  63.                     int cnt = 0;
  64.                     for (const auto &[w, x] : wadj[u]) {
  65.                         leaf &= x == par[u];
  66.                         cnt += x != par[u] && w;
  67.                     }
  68.                     for (const auto &[w, x] : wadj[u]) {
  69.                         if (x != par[u]) {
  70.                             d[x] = d[u]+1;
  71.                             par[x] = u;
  72.                             if (w && cnt == 1) {
  73.                                 head[x] = head[u];
  74.                                 f(f, x, u);
  75.                                 end[u] = end[x];
  76.                             } else {
  77.                                 f(f, x, -1);
  78.                             }
  79.                         }
  80.                     }
  81.                 };
  82.                 dfs(dfs, rt, -1);
  83.                 int metric = 0;
  84.                 for (int j = 0; j < n; j += 1) {
  85.                     int tot = 1;
  86.                     int x = j;
  87.                     while (x != rt) {
  88.                         if (head[x] != x) {
  89.                             if (end[x] == x) {
  90.                                 tot += 1;
  91.                             } else {
  92.                                 tot += min(__lg(d[end[x]]-d[head[x]]+1-1)+2, d[x]-d[head[x]]+1);
  93.                             }
  94.                             x = head[x];
  95.                             if (x != rt) {
  96.                                 x = par[x];
  97.                             } else {
  98.                                 tot -= 1;
  99.                                 break;
  100.                             }
  101.                         } else {
  102.                             x = par[x];
  103.                             tot += 1;
  104.                         }
  105.                     }
  106.                     metric = max(metric, tot);
  107.                 }
  108.                 if (metric < mini) {
  109.                     mini_i = i;
  110.                     mini_rt = rt;
  111.                     mini = metric;
  112.                 }
  113.             }
  114.         }
  115.         for (auto &[u, v] : edges) {
  116.             cout << u+1 << " " << v+1 << "\n";
  117.         }
  118.         cout << "\n";
  119.         for (int i = 0; i < n-1; i += 1) {
  120.             if (mini_i&(1<<i)) {
  121.                 cout << edges[i].first+1 << " " << edges[i].second+1 << "\n";
  122.             }
  123.         }
  124.         cout << mini_i << " " << mini_rt << " = heavy edges, root\n";
  125.         cout << mini << "!\n";
  126.         cout << "==================================\n";
  127.     };
  128.     go();
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!