Advertisement
radmickey

Untitled

Jan 5th, 2023
1,045
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. struct Node {
  6.     Node* left;
  7.     Node* right;
  8.     int value;
  9.     int height;
  10.  
  11.     explicit Node(int value, Node* l = nullptr, Node* r = nullptr) {
  12.         left = l;
  13.         right = r;
  14.         this->value = value;
  15.         height = 1;
  16.     }
  17.  
  18.     Node() {
  19.         height = 1;
  20.         value = 0;
  21.         left = nullptr;
  22.         right = nullptr;
  23.     }
  24. };
  25.  
  26.  
  27. class AVL {
  28. private:
  29.     static int height(Node* cur) {
  30.         return cur ? cur->height : 0;
  31.     }
  32.  
  33.     static int bFactor(Node* cur) {
  34.         if (cur) {
  35.             return height(cur->right) - height(cur->left);
  36.         }
  37.         return 0;
  38.     }
  39.  
  40.     static void fixHeight(Node* cur) {
  41.         cur->height = std::max(height(cur->right), height(cur->left)) + 1;
  42.     }
  43.  
  44.     Node* beBalance(Node* cur) {
  45.         fixHeight(cur);
  46.         if (bFactor(cur) == 2) {
  47.             if (bFactor(cur->right) < 0) {
  48.                 cur->right = rotateRight(cur->right);
  49.             }
  50.  
  51.             return rotateLeft(cur);
  52.  
  53.         } else if (bFactor(cur) == -2) {
  54.             if (bFactor(cur->left) > 0) {
  55.                 cur->left = rotateLeft(cur->left);
  56.             }
  57.  
  58.             return rotateRight(cur);
  59.         }
  60.         return cur;
  61.     }
  62.  
  63.  
  64.     Node* add(int x, Node* cur) {
  65.         if (!cur) {
  66.             return new Node(x);
  67.         }
  68.  
  69.         if (cur->value < x) {
  70.             cur->right = add(x, cur->right);
  71.         } else {
  72.             cur->left = add(x, cur->left);
  73.         }
  74.  
  75.         return beBalance(cur);
  76.     }
  77.  
  78.     static Node* rotateRight(Node* y) {
  79.         Node* x = y->left;
  80.         y->left = x->right;
  81.         x->right = y;
  82.         fixHeight(y);
  83.         fixHeight(x);
  84.         return x;
  85.     }
  86.  
  87.     Node* rotateLeft(Node* x) {
  88.         Node* y = x->right;
  89.         x->right = y->left;
  90.         y->left = x;
  91.         fixHeight(x);
  92.         fixHeight(y);
  93.         return y;
  94.     }
  95.  
  96.     Node* remove_(int x, Node* cur) {
  97.  
  98.         if (cur == nullptr) {
  99.             return nullptr;
  100.         }
  101.  
  102.         if (cur->value == x) {
  103.             if (cur->right == nullptr && cur->left == nullptr) {
  104.                 delete cur;
  105.                 return nullptr;
  106.             }
  107.  
  108.             if (cur->left == nullptr) {
  109.                 Node* right = cur->right;
  110.                 delete cur;
  111.                 return right;
  112.             }
  113.  
  114.             if (cur->right == nullptr) {
  115.                 Node* left = cur->left;
  116.                 delete cur;
  117.                 return left;
  118.             }
  119.  
  120.             // If the node has two "children"
  121.  
  122.             Node* max_node = cur->left;
  123.             cur->height--;
  124.             if (cur->left->right == nullptr) {
  125.                 cur->left->height--;
  126.             }
  127.  
  128.             while (max_node->right) {
  129.                 max_node->height--;
  130.                 max_node = max_node->right;
  131.             }
  132.  
  133.             cur->value = max_node->value;
  134.             cur->left = remove_(max_node->value, cur->left);
  135.  
  136.         } else {
  137.             if (cur->value < x) {
  138.                 cur->right = remove_(x, cur->right);
  139.             } else {
  140.                 cur->left = remove_(x, cur->left);
  141.             }
  142.         }
  143.         return beBalance(cur);
  144.     }
  145. public:
  146.     std::vector<int> all_elems;
  147.     Node* root;
  148.  
  149.     AVL() {
  150.         root = nullptr;
  151.     }
  152.  
  153.     bool exist(int x) const {
  154.         Node* root_copy = this->root;
  155.         while (root_copy) {
  156.             if (x > root_copy->value) {
  157.                 root_copy = root_copy->right;
  158.             } else if (x < root_copy->value) {
  159.                 root_copy = root_copy->left;
  160.             } else {
  161.                 return true;
  162.             }
  163.         }
  164.         return false;
  165.     }
  166.  
  167.     void insert(int x) {
  168.         if (exist(x)) {
  169.             return;
  170.         }
  171.  
  172.         root = add(x, root);
  173.     }
  174.  
  175.     void remove(int x) {
  176.         if (exist(x)) {
  177.             if (root->value == x && root->height == 1) {
  178.                 delete root;
  179.                 root = nullptr;
  180.                 return;
  181.             }
  182.             root = remove_(x, root);
  183.         }
  184.     }
  185.  
  186.     int getBalanceRoot() const {
  187.         return bFactor(root);
  188.     }
  189.     int getHeight(Node* cur) const {
  190.         return cur->height;
  191.     }
  192. };
  193.  
  194.  
  195. struct Node_graph {
  196.     int64_t a;
  197.     int64_t b;
  198.     int num;
  199.     bool isValid;
  200.     AVL pot;
  201.     std::vector<std::pair<Node_graph*, int>> potions;
  202.     Node_graph() {
  203.         a = 0;
  204.         b = 0;
  205.         isValid = true;
  206.     }
  207. };
  208.  
  209. std::pair<int64_t, int64_t> BFS (Node_graph* nodeGraph, int n) {
  210.     if (!nodeGraph->isValid) {
  211.         return {0, 0};
  212.     }
  213.  
  214.     std::queue<std::pair<Node_graph*, int64_t>> q;
  215.     q.push({nodeGraph, 1});
  216.     std::vector<bool> used(n + 1);
  217.     used[nodeGraph->num] = true;
  218.  
  219.  
  220.     int64_t a = nodeGraph->a;
  221.     int64_t b = nodeGraph->b;
  222.  
  223.     while (!q.empty()) {
  224.         Node_graph* v = q.front().first;
  225.         int64_t count = q.front().second;
  226.         q.pop();
  227.  
  228.         for (size_t i = 0; i < v->potions.size(); i++) {
  229.             Node_graph* to = v->potions[i].first;
  230.  
  231.             if (!to->isValid) {
  232.                 v->isValid = false;
  233.                 nodeGraph->isValid = false;
  234.                 return {a, b};
  235.             }
  236.  
  237.             if (!used[to->num]) {
  238.                 used[to->num] = true;
  239.                 if (to->num > v->num) {
  240.                     q.push({to, v->potions[i].second});
  241.                 } else {
  242.                     if (!to->isValid) {
  243.                         v->isValid = false;
  244.                         nodeGraph->isValid = false;
  245.                         return {a, b};
  246.                     }
  247.                 }
  248.                 a += v->potions[i].second * to->a * count;
  249.                 b += v->potions[i].second * to->b * count;
  250.             } else {
  251.                 nodeGraph->isValid = false;
  252.                 return {a, b};
  253.             }
  254.         }
  255.     }
  256.     return {a, b};
  257. }
  258.  
  259. int main() {
  260.  
  261.     std::ios::sync_with_stdio(false);
  262.     std::cin.tie(nullptr);
  263.  
  264.     int n;
  265.     std::cin >> n;
  266.  
  267.     std::vector<Node_graph*> graph(n - 2);
  268.  
  269.     for (auto & i : graph) {
  270.         i = new Node_graph;
  271.     }
  272.  
  273.     int count;
  274.     int type;
  275.     for (int i = 0; i < n - 2; i++) {
  276.         graph[i]->num = i + 3;
  277.         std::cin >> count;
  278.         if (count == 0) {
  279.             graph[i]->isValid = false;
  280.         }
  281.         while (count--) {
  282.             std::cin >> type;
  283.             if (type == 1) {
  284.                 graph[i]->a++;
  285.             } else if (type == 2) {
  286.                 graph[i]->b++;
  287.             } else {
  288.                 if (graph[i]->pot.exist(type)) {
  289.                     for (auto& t: graph[i]->potions) {
  290.                         if (t.first == graph[type - 3]) {
  291.                             t.second++;
  292.                             break;
  293.                         }
  294.                     }
  295.                 } else {
  296.                     graph[i]->potions.emplace_back(graph[type - 3], 1);
  297.                     graph[i]->pot.insert(type);
  298.                 }
  299.             }
  300.         }
  301.     }
  302.  
  303.     for (Node_graph*& nodeGraph : graph) {
  304.         std::pair<int64_t, int64_t> t = BFS(nodeGraph, n);
  305.         nodeGraph->a = t.first;
  306.         nodeGraph->b = t.second;
  307.     }
  308.  
  309.     int q;
  310.     std::cin >> q;
  311.     int a;
  312.     int b;
  313.     int potion;
  314.     while (q--) {
  315.         std::cin >> a >> b >> potion;
  316.  
  317.         if (graph[potion - 3]->isValid) {
  318.             if (graph[potion - 3]->a <= a && graph[potion - 3]->b <= b) {
  319.                 std::cout << 1;
  320.             } else {
  321.                 std::cout << 0;
  322.             }
  323.         } else {
  324.             std::cout << 0;
  325.         }
  326.  
  327.     }
  328. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement