fork download
copy 
  1. #include <iostream>
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. const string invalid="Invalid command";
  8. const string ok="OK";
  9.  
  10. struct Node 
  11. {
  12.  
  13.     string name;
  14.     map<string, Node*> children;
  15.     Node* parent;
  16.     int size;
  17.  
  18.     Node(string name)
  19.     {
  20.       this->name=name;
  21.       parent=nullptr;
  22.       size=1;
  23.     }
  24. };
  25.  
  26. vector<string> splitPath(string& path) 
  27. {
  28.     vector<string> parts;
  29.     stringstream ss(path);
  30.     string part;
  31.     while (getline(ss, part, '/')) 
  32.     {
  33.         if (!part.empty()) {
  34.             parts.push_back(part);
  35.         }
  36.     }
  37.     return parts;
  38. }
  39.  
  40. vector<string> splitCommand(string& command) 
  41. {
  42.     vector<string> parts;
  43.     stringstream ss(command);
  44.     string part;
  45.     // while (ss >> part) {
  46.     //     parts.push_back(part);
  47.     // }
  48.     while(getline(ss,part,' '))
  49.     {
  50.       if(!part.empty()) parts.push_back(part);
  51.     }
  52.     return parts;
  53. }
  54.  
  55. class Tree 
  56. {
  57. private:
  58.     Node* root;
  59.     int totalNodes;
  60.  
  61.     Node* getNode(vector<string>& parts) //o log n
  62.     {
  63.         if (parts.empty() || parts[0] != root->name) return nullptr;
  64.         Node* current = root;
  65.         for (int i = 1; i < parts.size(); i++) 
  66.         {
  67.             auto it = current->children.find(parts[i]);
  68.             if (it == current->children.end()) return nullptr;
  69.             current = it->second;
  70.         }
  71.         return current;
  72.     }
  73.  
  74.     bool isAncestor(Node* src, Node* dest) //o log n
  75.     {
  76.         Node* current = dest;
  77.         while (current != nullptr) 
  78.         {
  79.             if (current == src) return true;
  80.             current = current->parent;
  81.         }
  82.         return false;
  83.     }
  84.  
  85.     Node* copyTree(Node* src) //o(n)
  86.     {
  87.         Node* copy = new Node(src->name);
  88.         copy->size = src->size;
  89.         totalNodes++;
  90.         for (auto& c : src->children) 
  91.         {
  92.             Node* childCopy = copyTree(c.second);
  93.             childCopy->parent = copy;
  94.             copy->children[c.first] = childCopy;
  95.         }
  96.         return copy;
  97.     }
  98.  
  99.     void computeSizes(Node* node) //o(n)
  100.     {
  101.         // if (!node) return;
  102.         node->size = 1;
  103.         for (auto& c : node->children) 
  104.         {
  105.             computeSizes(c.second);
  106.             node->size += c.second->size;
  107.         }
  108.     }
  109.  
  110. public:
  111.     Tree(vector<string>& lines) 
  112.     {
  113.         if (lines.empty()) 
  114.         {
  115.             root = nullptr;
  116.             totalNodes = 0;
  117.             return;
  118.         }
  119.  
  120.         string firstLine = lines[0];
  121.         vector<string> tokens = splitCommand(firstLine);
  122.         if (tokens.empty()) 
  123.         {
  124.             root = nullptr;
  125.             totalNodes = 0;
  126.             return;
  127.         }
  128.  
  129.         root = new Node(tokens[0]);
  130.         totalNodes = 1;
  131.  
  132.         for (int i = 1; i < tokens.size(); ++i) 
  133.         {
  134.             Node* child = new Node(tokens[i]);
  135.             child->parent = root;
  136.             root->children[tokens[i]] = child;
  137.             totalNodes++;
  138.         }
  139.  
  140.         for (int i = 1; i < lines.size(); ++i) 
  141.         {
  142.             tokens = splitCommand(lines[i]);
  143.             if (tokens.empty()) continue;
  144.  
  145.             string parentPath = tokens[0];
  146.             vector<string> parentParts = splitPath(parentPath);
  147.             Node* parentNode = getNode(parentParts);
  148.             if (!parentNode) continue;
  149.  
  150.             for (int j = 1; j < tokens.size(); j++) {
  151.                 string childName = tokens[j];
  152.                 if (parentNode->children.count(childName)) continue;
  153.  
  154.                 Node* child = new Node(childName);
  155.                 child->parent = parentNode;
  156.                 parentNode->children[childName] = child;
  157.                 totalNodes++;
  158.             }
  159.         }
  160.  
  161.         computeSizes(root);
  162.     }
  163.  
  164.     //Possible that someone may have added a subtree to this node.
  165.     //Another possibility is the removal of subtree from any child of this node.
  166.     //TC-> o(length of path) -> o(log n)
  167.     string countDescendants(string& path) 
  168.     {
  169.         vector<string> parts = splitPath(path);
  170.         Node* node = getNode(parts);
  171.         if (!node) return invalid;
  172.         return to_string(node->size - 1);
  173.     }
  174.  
  175. //
  176.     string cutPaste(string& src, string& dest) //O(log N)
  177.     {
  178.         vector<string> srcParts = splitPath(src);//length of path-> log n
  179.         vector<string> destParts = splitPath(dest);
  180.         Node* srcNode = getNode(srcParts);
  181.         Node* destNode = getNode(destParts);
  182.  
  183.         if (!srcNode || !destNode) return invalid;
  184.         if (srcNode == destNode) return invalid;
  185.         if (isAncestor(srcNode, destNode)) return invalid;//o log n
  186.         // if(isAncestor(destNode,srcNode)) return invalid;// log n
  187.  
  188.         //do we need to check this?
  189.         if (destNode->children.count(srcNode->name)) return invalid;
  190.  
  191.  
  192.         //actual work starts here
  193.         //remove node from previous parent
  194.         Node* oldParent = srcNode->parent;
  195.         if (!oldParent) return invalid;
  196.         oldParent->children.erase(srcNode->name);//o log(children)
  197.  
  198.         int diff = srcNode->size;
  199.         Node* current = oldParent;
  200.         while (current) //o log n
  201.         {
  202.             current->size -= diff;
  203.             current = current->parent;
  204.         }
  205.  
  206.         //add node to new parent ie destination
  207.         srcNode->parent = destNode;
  208.         destNode->children[srcNode->name] = srcNode; //o log (children)
  209.  
  210.  
  211.         current = destNode;
  212.         while (current)//o(logn)
  213.         {
  214.             current->size += diff;
  215.             current = current->parent;
  216.         }
  217.  
  218.         return ok;
  219.     }
  220.  
  221.     string copyPaste(string& src, string& dest) //o(n)
  222.     {
  223.         vector<string> srcParts = splitPath(src);
  224.         vector<string> destParts = splitPath(dest);
  225.         Node* srcNode = getNode(srcParts);
  226.         Node* destNode = getNode(destParts);
  227.  
  228.         if (!srcNode || !destNode) return invalid;
  229.         if (isAncestor(srcNode, destNode)) return invalid;
  230.         // if(isAncestor(destNode,srcNode)) return invalid;
  231.         if (destNode->children.count(srcNode->name)) return invalid;
  232.         if (totalNodes + srcNode->size > 1e6) return invalid;
  233.  
  234.         //copy tree
  235.         Node* copiedSubtree = copyTree(srcNode);//O(n);// number of desc.
  236.  
  237.         destNode->children[copiedSubtree->name] = copiedSubtree;
  238.         copiedSubtree->parent = destNode;
  239.  
  240.         int diff = copiedSubtree->size;
  241.         Node* current = destNode;
  242.         while (current) 
  243.         {
  244.             current->size += diff;
  245.             current = current->parent;
  246.         }
  247.  
  248.         totalNodes += srcNode->size;
  249.         return ok;
  250.     }
  251. };
  252.  
  253. int main() 
  254. {
  255.     // ios_base::sync_with_stdio(false);
  256.     // cin.tie(nullptr);
  257.  
  258.     int n, q;
  259.     cin >> n >> q;
  260.     cin.ignore();
  261.  
  262.     vector<string> lines(n);
  263.     for (int i = 0; i < n; ++i)
  264.     {
  265.         string line;
  266.         getline(cin, line);
  267.         lines[i] = line;
  268.     }
  269.  
  270.     Tree tree(lines);
  271.  
  272.     for (int i = 0; i < q; ++i)
  273.     {
  274.         string command;
  275.         getline(cin, command);
  276.         vector<string> parts = splitCommand(command);
  277.  
  278.         if (parts.empty()) {
  279.             cout << invalid << endl;
  280.             continue;
  281.         }
  282.  
  283.         string cmd = parts[0];
  284.         if (cmd == "countDescendants")
  285.         {
  286.             if (parts.size() != 2) {
  287.                 cout << invalid << endl;
  288.             } else {
  289.                 cout << tree.countDescendants(parts[1]) << endl;
  290.             }
  291.         } else if (cmd == "cutPaste") {
  292.             if (parts.size() != 3) {
  293.                 cout << invalid << endl;
  294.             } else {
  295.                 cout << tree.cutPaste(parts[1], parts[2]) << endl;
  296.             }
  297.         } else if (cmd == "copyPaste") {
  298.             if (parts.size() != 3) {
  299.                 cout << invalid << endl;
  300.             } else {
  301.                 cout << tree.copyPaste(parts[1], parts[2]) << endl;
  302.             }
  303.         } else {
  304.             cout << invalid << endl;
  305.         }
  306.     }
  307.  
  308.     return 0;
  309. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
3 6
root a b c
root/a d e
root/c f g
countDescendants root
countDescendants root/a
copyPaste root/a/d root/b
cutPaste root/c/f root/b
countDescendants root/b
countDescendants root/c/f
stdout
copy 
7
2
OK
OK
2
Invalid command
https://ideone.com/406At2
language:
C++14 (gcc 8.3)
created:
7 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!