Advertisement
Infernale

Ultimate Dragon [Binary Tree] [TLE]

Jan 11th, 2019
433
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.63 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MAX 1000000005
  4.  
  5. int size, queries, temp, count, idx, weight;
  6.  
  7. struct node{
  8.     int key;
  9.     int count;
  10.     int smaller;
  11.     struct node *left, *right;
  12. };
  13.  
  14. void inorder(struct node *root){
  15.     if(root!=NULL){
  16.         inorder(root->left);
  17.         printf("%d(%d) --> %d\n", root->key, root->count, root->smaller);
  18.         inorder(root->right);
  19.     }
  20. }
  21.  
  22. void modifyWeight(struct node *root){
  23.     if(root!=NULL){
  24.         modifyWeight(root->right);
  25.         root->smaller = size-(weight++);
  26.         modifyWeight(root->left);
  27.     }
  28. }
  29.  
  30. struct node *newNode(int item){
  31.     struct node *temp = (struct node*)malloc(sizeof(struct node));
  32.     temp->key = item;
  33.     temp->left = temp->right = NULL;
  34.     temp->count =  1;
  35.     return temp;
  36. }
  37.  
  38. struct node* insert(struct node* node, int key){
  39.     if(node==NULL){
  40.         return newNode(key);
  41.     }
  42.     if(key < node->key){
  43.         node->left = insert(node->left, key);  
  44.     }else if(key > node->key){
  45.         node->right = insert(node->right, key);    
  46.     }else if(key == node->key){
  47.         (node->count)++;
  48.     }
  49.     return node;
  50. }
  51.  
  52. int findWeight(struct node *root, int key){
  53.     //printf("Node now %d\n", root->key);
  54.     if(root==NULL){
  55.         return -1;
  56.     }
  57.     if(root->key<=key){
  58.         return root->smaller;
  59.     }
  60.     if(root->key>key){
  61.         return findWeight(root->left, key);
  62.     }
  63. }
  64.  
  65. int main(){
  66.     scanf("%d %d",&size ,&queries);
  67.     struct node *root = NULL;
  68.     root = insert(root, MAX);
  69.     for(int i=0;i<size;i++){
  70.         scanf("%d", &temp);
  71.         insert(root, temp);
  72.     }
  73.     modifyWeight(root);
  74.     inorder(root);
  75.     for(int i=0;i<queries;i++){
  76.         count = 0;
  77.         scanf("%d", &temp);
  78.         findWeight(root, temp);
  79.         printf("Out : %d\n", findWeight(root, temp));
  80.     }
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement