fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /* A binary tree node has data, pointer to left child
  5.    and a pointer to right child */
  6. struct Node
  7. {
  8.     int data;
  9.     struct Node* left;
  10.     struct Node* right;
  11. };
  12.  
  13.  
  14. /* Helper function that allocates a new node with the
  15.    given data and NULL left and right pointers. */
  16. struct Node* newNode(int data)
  17. {
  18.   struct Node* node = (struct Node*)
  19.                        malloc(sizeof(struct Node));
  20.   node->data = data;
  21.   node->left = NULL;
  22.   node->right = NULL;
  23.  
  24.   return(node);
  25. }
  26.  
  27.  
  28. int findLevel(Node *root,int k,int level)
  29. {
  30.     if(root==NULL)
  31.         return -1;
  32.     if(root->data ==k)
  33.         return level;
  34.     int l = findLevel(root->left,k,level+1);
  35.     return (l!=-1)?l:findLevel(root->right,k,level+1);
  36. }
  37.  
  38. Node *findDistU(Node *root,int n1,int n2,int &d1,int &d2,int &dist,int lvl)
  39. {
  40.     if(root==NULL)
  41.         return NULL;
  42.     if(root->data==n1)
  43.     {
  44.         d1 = lvl;
  45.         return root;
  46.     }
  47.     if(root->data==n2)
  48.     {
  49.         d2 = lvl;
  50.         return root;
  51.     }
  52.  
  53.     Node *l = findDistU(root->left,n1,n2,d1,d2,dist,lvl+1);
  54.     Node *r = findDistU(root->right,n1,n2,d1,d2,dist,lvl+1);
  55.  
  56.     if(l and r)
  57.     {
  58.         dist = d1+d2-2*lvl;
  59.     }
  60.     return (l!=NULL)? l :r;
  61. }
  62. int findDist(Node *root,int n1,int n2)
  63. {
  64.     int d1=-1,d2=-1,dist;
  65.     Node *lca = findDistU(root,n1,n2,d1,d2,dist,1);
  66.     if(d1!=-1 and d2!=-1)
  67.     {
  68.        return dist;
  69.     }
  70.  
  71.     if(d1!=-1)
  72.     {
  73.         dist = findLevel(lca,n2,0);
  74.         return dist;
  75.     }
  76.     if(d2!=-1)
  77.     {
  78.         dist = findLevel(lca,n1,0);
  79.         return dist;
  80.     }
  81.     return -1;
  82. }
  83.  
  84.  
  85. /* Driver program to test size function*/
  86. int main()
  87. {
  88.   int t;
  89.   struct Node *child;
  90.   scanf("%d\n", &t);
  91.   while (t--)
  92.   {
  93.      map<int, Node*> m;
  94.      int n;
  95.      scanf("%d\n",&n);
  96.      struct Node *root = NULL;
  97.      if(n==1)
  98.      {
  99.         int a;
  100.         cin>>a;
  101.         cout<<a<<endl;
  102.      }else{
  103.      while (n--)
  104.      {
  105.         Node *parent;
  106.         char lr;
  107.         int n1, n2;
  108.         scanf("%d %d %c", &n1, &n2, &lr);
  109.       //  cout << n1 << " " << n2 << " " << (char)lr << endl;
  110.         if (m.find(n1) == m.end())
  111.         {
  112.            parent = newNode(n1);
  113.            m[n1] = parent;
  114.            if (root == NULL)
  115.              root = parent;
  116.         }
  117.         else
  118.            parent = m[n1];
  119.  
  120.         child = newNode(n2);
  121.         if (lr == 'L')
  122.           parent->left = child;
  123.         else
  124.           parent->right = child;
  125.         m[n2]  = child;
  126.      }
  127.      int a,b;
  128.      cin>>a>>b;
  129.  
  130.      cout<<findDist(root,a,b)<<endl;
  131.  
  132.   }
  133.   }
  134.   return 0;
  135. }
  136.  
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
13
2
1 2 R 1 3 L
2 3
4
10 20 L 10 30 R 20 40 L 20 60 R
20 60
6
1 2 R 2 4 R 4 5 R 5 6 R 6 7 R 7 8 L
2 7
4
1 10 L 1 20 R 20 30 L 30 40 R
10 30
6
100 20 R 20 30 L 30 40 L 40 50 R 50 60 L 50 70 R
100 70
4
20 10 L 10 5 L 5 1 L 1 50 R
20 50
4
20 10 L 10 5 L 5 2 L 2 3 R
2 3
6
20 10 L 10 5 L 5 2 L 2 3 R 20 30 R 30 15 L
10 5
6
20 10 L 10 5 L 5 2 L 2 3 R 20 30 R 30 25 L
25 3
7
1 2 L 2 3 L 3 4 L 3 5 R 4 6 L 6 7 R 7 8 L
3 6
6
1 2 L 1 3 R 2 4 L 2 5 R 3 6 L 3 7 R
2 6
7
20 8 L 20 22 R 8 4 L 8 12 R 12 10 L 12 14 R 22 25 R
12 22
10
50 60 L 50 70 R 60 80 L 60 90 R 80 93 L 80 94 R 90 95 L 90 96 R 70 91 L 70 92 R
50 92
stdout
copy 
2
1
4
3
5
4
1
1
6
2
3
3
2
https://ideone.com/XNAJCv
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!