Art_Uspen

Untitled

May 17th, 2021
517
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3. #include <string>
  4. #include <utility>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. struct Node {
  10.     int64_t number;
  11.     string key;
  12.     string color;
  13.     bool is_BTS;
  14.     bool is_Colored;
  15.     Node *left, *right, *parent;
  16. public:
  17.     Node();
  18.  
  19.     explicit Node(string key, string color);
  20.  
  21.     void Check_BTS(Node *vert);
  22.  
  23.     void Check_Colored(Node *vert);
  24. };
  25.  
  26. Node::Node() :
  27.         number(-1),
  28.         is_BTS(true),
  29.         is_Colored(true),
  30.         left(nullptr), right(nullptr), parent(nullptr) {}
  31.  
  32. Node::Node(string key_, string color_) :
  33.         number(-1),
  34.         key(std::move(key_)),
  35.         color(std::move(color_)),
  36.         is_BTS(true),
  37.         is_Colored(true),
  38.         left(nullptr), right(nullptr), parent(nullptr) {}
  39.  
  40. void Node::Check_BTS(Node *vert) {
  41.     if (vert->left != nullptr) {
  42.         Check_BTS(vert->left);
  43.     }
  44.     if (vert->key == "null") {
  45.         return;
  46.     }
  47.     string left_key = vert->left->key;
  48.     string right_key = vert->right->key;
  49.     if (left_key != "null" && right_key != "null") {
  50.         if (!(stold(left_key) < stold(vert->key) && stold(vert->key) < stold(right_key))) {
  51.             is_BTS = false;
  52.         }
  53.     } else if (left_key != "null" && right_key == "null") {
  54.         if (!(stold(left_key) < stold(vert->key))) {
  55.             is_BTS = false;
  56.         }
  57.     } else if (left_key == "null" && right_key != "null") {
  58.         if (!(stold(vert->key) < stold(right_key))) {
  59.             is_BTS = false;
  60.         }
  61.     }
  62.     if (vert->right != nullptr) {
  63.         Check_BTS(vert->right);
  64.     }
  65. }
  66.  
  67. void Node::Check_Colored(Node *vert) {
  68.     if (vert->left != nullptr) {
  69.         Check_Colored(vert->left);
  70.     }
  71.     if (vert->parent == nullptr && vert->color != "B") {//для корня
  72.         is_Colored = false;
  73.         return;
  74.     }
  75.     if (vert->color == "R") {
  76.         if (vert->parent->color != "B") {
  77.             is_Colored = false;
  78.         }
  79.     }
  80.     if (vert->right != nullptr) {
  81.         Check_Colored(vert->right);
  82.     }
  83. }
  84.  
  85. void Find_leaves(Node *vert, vector<Node *> &seq) {
  86.     if (vert->left != nullptr) {
  87.         Find_leaves(vert->left, seq);
  88.     }
  89.     if (vert->left == nullptr && vert->right == nullptr) {
  90.         seq.push_back(vert);
  91.     }
  92.     if (vert->right != nullptr) {
  93.         Find_leaves(vert->right, seq);
  94.     }
  95. }
  96.  
  97. int64_t Count_black(Node *vert) {
  98.     int64_t count = 0;
  99.     while (vert != nullptr) {
  100.         ++count;
  101.         vert = vert->parent;
  102.     }
  103.     return count;
  104. }
  105.  
  106.  
  107. int main() {
  108.     Node bts;
  109.     Node *root = nullptr;
  110.     int64_t N;
  111.     cin >> N;
  112.     if (N == 0) {
  113.         cout << "YES\n";
  114.         return 0;
  115.     }
  116.     vector<Node *> nodes(N);
  117.     int64_t n_root;
  118.     cin >> n_root;
  119.     --n_root;
  120.     for (int64_t i = 0; i < N; ++i) {
  121.         int64_t number;
  122.         string key, left, right, color;
  123.         cin >> number >> key >> left >> right >> color;
  124.         --number;
  125.         if (nodes[number] != nullptr) {
  126.             nodes[number]->key = key;
  127.             nodes[number]->color = color;
  128.         } else {
  129.             nodes[number] = new Node(key, color);
  130.             nodes[number]->number = number;
  131.         }
  132.         if (left != "null") {
  133.             int64_t n_left = stold(left) - 1;
  134.             if (nodes[n_left] == nullptr) {
  135.                 nodes[n_left] = new Node;
  136.             }
  137.             nodes[number]->left = nodes[n_left];
  138.             nodes[number]->left->number = n_left;
  139.             nodes[number]->left->parent = nodes[number];
  140.         } else {
  141.             nodes[number]->left = new Node("null", "B");
  142.             nodes[number]->left->parent = nodes[number];
  143.         }
  144.         if (right != "null") {
  145.             int64_t n_right = stold(right) - 1;
  146.             if (nodes[n_right] == nullptr) {
  147.                 nodes[n_right] = new Node;
  148.             }
  149.             nodes[number]->right = nodes[n_right];
  150.             nodes[number]->right->number = n_right;
  151.             nodes[number]->right->parent = nodes[number];
  152.         } else {
  153.             nodes[number]->right = new Node("null", "B");
  154.             nodes[number]->right->parent = nodes[number];
  155.         }
  156.         if (n_root == number) {
  157.             root = nodes[number];
  158.         }
  159.     }
  160.  
  161.     vector<Node *> seq;
  162.     Find_leaves(root, seq);
  163.     int64_t count = Count_black(seq[0]);
  164.     bool is_red_black = true;
  165.     for (const auto &item: seq) {
  166.         if (Count_black(item) != count) {
  167.             is_red_black = false;
  168.             break;
  169.         }
  170.     }
  171.     Node tree;
  172.     tree.Check_BTS(root);
  173.     tree.Check_Colored(root);
  174.     if (is_red_black && tree.is_BTS && tree.is_Colored) {
  175.         cout << "YES\n";
  176.     } else {
  177.         cout << "NO\n";
  178.     }
  179. }
RAW Paste Data