fork download 
  1. #include<iostream>
  2. #include<vector>
  3. #include<unordered_map>
  4. #include<map>
  5. #include<set>
  6. #include<queue>
  7. #include<list>
  8.  
  9. using namespace std;
  10.  
  11.  
  12. void solve(vector<int>tree)
  13. {
  14.     int n = tree.size() - 1;
  15.  
  16.     long long ans = 0;
  17.  
  18.     unordered_map<int, int>mp;
  19.  
  20.     for(int i=2; i<=n ; i++)
  21.     {
  22.         mp[tree[i]]++;
  23.     }
  24.  
  25.     priority_queue<int>hp;
  26.  
  27.     for(auto it=mp.begin(); it!=mp.end(); it++)
  28.     {
  29.         hp.push(it->second);
  30.     }
  31.  
  32.     hp.push(1);
  33.     multiset<int>right_list;
  34.  
  35.     while(!hp.empty() || !right_list.empty())
  36.     {
  37.         ans ++;
  38.         //spread
  39.         if(!right_list.empty())
  40.         {
  41.             auto it = right_list.begin();
  42.             while(it != right_list.end())
  43.             {
  44.                 if((*it) != 0)
  45.                 {
  46.                     int value = (*it);
  47.                     it = right_list.erase(it);
  48.                     value = value - 1;
  49.                     if(value > 0) right_list.insert(value);
  50.                 }
  51.                 else
  52.                 {
  53.                     it = right_list.erase(it);
  54.                 }
  55.             }
  56.         }
  57.  
  58.  
  59.         //infect and add to right_list
  60.  
  61.  
  62.         if(!hp.empty())
  63.         {
  64.             int topnode = hp.top();
  65.             hp.pop();
  66.  
  67.             //infected
  68.             topnode--;
  69.             if(topnode > 0)  right_list.insert(topnode);
  70.             //inserted in right list
  71.         }  
  72.         //************ */
  73.         //if heap is empty then also I can infect one from above rightlist using my infect operation greedily
  74.         //to decrease the total no.of operation required   
  75.         else if(!right_list.empty())
  76.         {
  77.             auto it = prev(right_list.end());
  78.             if((*it) != 0)
  79.             {
  80.                 int value = (*it);
  81.                 right_list.erase(it);
  82.                 value = value - 1;
  83.                 if(value > 0) right_list.insert(value);
  84.             }
  85.             else right_list.erase(it);
  86.         }   
  87.     }
  88.  
  89.     cout << ans << endl;
  90.  
  91.     return ;
  92. }
  93.  
  94.  
  95. int main()
  96. {
  97.     int number_of_test_cases;
  98.     int no_of_branches;
  99.  
  100.     cin >> number_of_test_cases;
  101.  
  102.     while(number_of_test_cases--)
  103.     {
  104.         cin >> no_of_branches;
  105.         vector<int>tree(no_of_branches+1, 0);
  106.         int index = 2;
  107.         while(no_of_branches > 1)
  108.         {
  109.             cin >> tree[index++]; 
  110.             no_of_branches--;
  111.         }
  112.  
  113.         solve(tree);
  114.  
  115.     }
  116.  
  117.     return 0;
  118. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5
7
1 1 1 2 2 4
5
5 5 1 4
2
1
3
3 1
6
1 1 1 1 1
stdout 
4
4
2
3
4
https://ideone.com/1jYO2g
language:
C++ (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!