fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. class node{
  6.  
  7.     public:
  8.  
  9.     int data;
  10.  
  11.     node *left, *right;
  12.  
  13.     node(int data__){
  14.  
  15.         data = data__;
  16.  
  17.         left = right = NULL;
  18.  
  19.     }
  20.  
  21. };
  22.  
  23. node* make_tree(vector<int> a){
  24.  
  25.     node *head = NULL, *ptr = NULL;
  26.  
  27.     int n = a.size();
  28.  
  29.     if(n == 0)
  30.  
  31.         return NULL;
  32.  
  33.     head = new node(a[0]);
  34.  
  35.     ptr = head;
  36.  
  37.     queue<node*> q;
  38.  
  39.     q.push(ptr);
  40.  
  41.     int i = 0;
  42.  
  43.     while(i < n and !q.empty()){
  44.  
  45.         ptr = q.front();
  46.  
  47.         q.pop();
  48.  
  49.         if(i < n and a[i] != -1){
  50.  
  51.             ptr -> left = new node(a[i]);
  52.  
  53.             i++;
  54.  
  55.             q.push(ptr -> left);
  56.  
  57.         }
  58.  
  59.         if(i < n and a[i] != -1){
  60.  
  61.             ptr -> right = new node(a[i]);
  62.  
  63.             i++;
  64.  
  65.             q.push(ptr -> right);
  66.  
  67.         }
  68.  
  69.  
  70.  
  71.     }
  72.  
  73.     return head;
  74.  
  75. }
  76.  
  77. node* ptr1(node* head, int k){
  78.  
  79.     if(head == NULL){
  80.  
  81.         return NULL;
  82.  
  83.     }
  84.  
  85.     if(head -> data == k){
  86.  
  87.         return head;
  88.  
  89.     }
  90.  
  91.     node* l = ptr1(head -> left, k);
  92.  
  93.     if(l)
  94.  
  95.         return l;
  96.  
  97.     node* r = ptr1(head -> right, k);
  98.  
  99.     return r;
  100.  
  101. }
  102.  
  103. int count(node* head){
  104.  
  105.     if(head == NULL)
  106.  
  107.     return 0;
  108.  
  109.     int l = count(head -> left);
  110.  
  111.     int r = count(head -> right);
  112.  
  113.     return 1 + l + r;
  114.  
  115. }
  116.  
  117. int main(){
  118.  
  119.     int n, x, k;
  120.  
  121.     cin >> n >> x >> k;
  122.  
  123.     vector<int> v(n);
  124.  
  125.     for(int i = 0; i < n; i++){
  126.  
  127.         int y;
  128.  
  129.         cin >> y;
  130.  
  131.         v.push_back(y);
  132.  
  133.     }
  134.  
  135.     node* head = make_tree(v);
  136.  
  137.     node* ptr = ptr1(head, k);
  138.  
  139.     int rightcount = count(ptr -> right);
  140.  
  141.     int leftcount = count(ptr -> left);
  142.  
  143.     if(rightcount > x - rightcount or leftcount > x - leftcount){
  144.  
  145.         cout << 1 << "\n";
  146.  
  147.     }
  148.  
  149.     else{
  150.  
  151.         cout << 0 << "\n";
  152.  
  153.     }
  154.  
  155. }
Success #stdin #stdout 0s 4192KB
comments (?)
stdin
copy 
7 3 1 
1 2 -1 -1 3 -1 -1
stdout
copy 
0
https://ideone.com/EYaYjY
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!