SHARE
TWEET

Untitled

mfgnik Jun 30th, 2020 1,099 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <set>
  3. #include <unordered_map>
  4. #include <string>
  5. #include <algorithm>
  6.  
  7.  
  8. int CalculateHeight(const std::string& name, const std::unordered_map<std::string, std::string>& tree,
  9.                     std::unordered_map<std::string, int>& heights) {
  10.     if (heights.count(name)) {
  11.         return heights[name];
  12.     }
  13.     if (!tree.count(name)) {
  14.         return heights[name] = 0;
  15.     }
  16.     return heights[name] = CalculateHeight(tree.at(name), tree, heights) + 1;
  17. }
  18.  
  19.  
  20. int main() {
  21.     std::unordered_map<std::string, std::string> tree;
  22.     std::unordered_map<std::string, int> heights;
  23.     std::set<std::string> names;
  24.     int amount;
  25.     std::cin >> amount;
  26.     for (int index = 0; index + 1 < amount; ++index) {
  27.         std::string child, parent;
  28.         std::cin >> child >> parent;
  29.         tree[child] = parent;
  30.         names.insert(child);
  31.         names.insert(parent);
  32.     }
  33.     for (const auto& name : names) {
  34.         std::cout << name << " " << CalculateHeight(name, tree, heights) << "\n";
  35.     }
  36. }
RAW Paste Data
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
Top