fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #pragma GCC target ("avx2")
  5. #pragma GCC optimization ("O3")
  6. #pragma GCC optimization ("unroll-loops")
  7.  
  8. #define xi first
  9. #define yi second
  10. #define MAX 200007
  11. #define INF 2000
  12. #define SQ 500
  13. #define all(a) a.begin(), a.end()
  14.  
  15. typedef long long ll;
  16. typedef long double ld;
  17. typedef long long ll;
  18. const ll md = 1e9 + 7;
  19. vector<vector<int>>adj;
  20. vector<int> dep, del, pr;
  21. vector<pair<int, int>>a;
  22. void dfs_1(int node) {
  23.     a.push_back({dep[node], node});
  24.     for (auto &i : adj[node]) {
  25.         dep[i] = dep[node] + 1;
  26.         pr[i] = node;
  27.         dfs_1(i);
  28.     }
  29. }
  30. void dfs_2(int node) {
  31.     del[node] = true;
  32.     for (auto &i : adj[node]) {
  33.         if (del[i]) continue;
  34.         dfs_2(i);
  35.     }
  36. }
  37. int getMinimumHierarchyHeight(int hierarchy_nodes, vector<int> hierarchy_from, vector<int> hierarchy_to, int max_reassignments) {
  38.     int n = hierarchy_nodes;
  39.     adj = vector<vector<int>>(n + 1);
  40.     pr = dep = del = vector<int> (n + 1);
  41.     a = vector<pair<int, int>> (n + 1);
  42.     for (auto i = 0; i < hierarchy_from.size(); i++) {
  43.         adj[hierarchy_from[i]].emplace_back(hierarchy_to[i]);
  44.     }
  45.     dfs_1(1);
  46.     sort(a.rbegin(), a.rend());
  47.     int l = 0, r = a.begin()->first;
  48.     while (l + 1 < r) {
  49.         int mid = (l + r) / 2;
  50.         int need = 0;
  51.         fill(del.begin(), del.end(), 0);
  52.         for (auto &[d, node]: a) {
  53.             if (dep[node] <= mid) break;
  54.             int u = node;
  55.             int cnt = mid - 1;
  56.             while (!del[u] && cnt > 0 && pr[u] != 1) {
  57.                 u = pr[u];
  58.                 cnt--;
  59.             }
  60.             if (!del[u]) {
  61.                 dfs_2(u);
  62.                 need++;
  63.             }
  64.         }
  65.         if (need > max_reassignments) l = mid;
  66.         else r = mid;
  67.     }
  68.     return r;
  69. }
  70. int main() {
  71.     ios::sync_with_stdio(false);
  72.     cin.tie(nullptr);
  73.  
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/k7dvCv
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!