fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<unordered_map>
  4. using namespace std;
  5.  
  6.  
  7.  
  8.  
  9. int main()
  10. {
  11.     vector<int>S = {4, 5};
  12.  
  13.     vector<pair<int, int> >tree;
  14.  
  15.     tree.push_back({1,2});
  16.     tree.push_back({2,3});
  17.     tree.push_back({3,4});
  18.     tree.push_back({4,5});
  19.     // tree.push_back({2,6});
  20.     // tree.push_back({4,7});
  21.     // tree.push_back({7,8});
  22.  
  23.     vector<int>parent(tree.size() + 2);
  24.  
  25.     parent[1] = -1;
  26.  
  27.     for(auto edge: tree)
  28.     {
  29.         parent[edge.second] = edge.first;
  30.     }
  31.  
  32.     unordered_map<int, bool>edge_tracker(false);
  33.  
  34.     for(auto node: S)
  35.     {
  36.         int current_node = node;
  37.         int parent_node;
  38.         while(parent[current_node] != -1)
  39.         {
  40.             parent_node = parent[current_node];
  41.             if(edge_tracker.count(parent_node + current_node)) break;
  42.             else edge_tracker[parent_node + current_node] = true;
  43.             current_node = parent_node;
  44.         }
  45.     }
  46.  
  47.     cout << "final ans: " << 2*(edge_tracker.size()) << endl;
  48.  
  49.     return 0;
  50. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
final ans: 8
https://ideone.com/oAIxsq
language:
C++ (gcc 8.3)
created:
1 day 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!