Art_Uspen

Untitled

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