SHARE
TWEET

UVA - Phone List (trie tree)

jakaria_hossain May 8th, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int flag;
  4. int last,cur, len,id;
  5. string str;
  6. struct node
  7. {
  8.     bool endmark;
  9.     int next[13];
  10.  
  11. } root[100000];
  12. void trie(int cur)
  13. {
  14.     for (int i = 0; i < 10; i++)
  15.         root[cur].next[i] = -1;
  16.  
  17.     root[cur].endmark=false;
  18. }
  19. void insert()
  20. {
  21.     cur=0;
  22.     len=str.size();
  23.     for (int i = 0; i < len; i++)
  24.     {
  25.         id = str[i] - 48;
  26.         if (root[cur].next[id]==-1)
  27.         {
  28.             root[cur].next[id]=last;
  29.             trie(last++);
  30.             cur = root[cur].next[id];
  31.         }
  32.         else
  33.         {
  34.             cur = root[cur].next[id];
  35.             if(root[cur].endmark==true)
  36.             {
  37.                 flag=1;
  38.             }
  39.             if(i==len-1)
  40.                 flag = 1;
  41.         }
  42.         if(flag==1)
  43.             break;
  44.     }
  45.     root[cur].endmark = true;
  46. }
  47.  
  48.  
  49. int main()
  50. {
  51.  
  52.     int test;
  53.     cin>>test;
  54.     while(test--)
  55.     {
  56.         flag=0;
  57.         last=1;
  58.         trie(0);
  59.         int n;
  60.         cin>>n;
  61.         for(int i=0; i<n; i++)
  62.         {
  63.             cin>>str;
  64.             insert();
  65.         }
  66.         if(flag==1)
  67.             cout<<"NO"<<endl;
  68.         else
  69.             cout<<"YES"<<endl;
  70.     }
  71.     return 0;
  72. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top