fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct node{
  4.     int cnt_trees;
  5.     node *next[10];
  6.     node(){
  7.         cnt_trees=0;
  8.         for(int i=0;i<10;i++)next[i]=NULL;
  9.     }
  10. }*root;
  11.  
  12. void insert_into_Trie(string str){
  13.     node *cur=root;
  14.     for(int i=0;str[i];i++){
  15.         int id=str[i]-'0';
  16.         if(cur->next[id]==NULL)
  17.             cur->next[id]=new node();
  18.             cur=cur->next[id];
  19.     }
  20.     cur->cnt_trees++;
  21.     //cout<<cur->cnt_trees<<endl;
  22. }
  23.  
  24. bool search(string str){
  25.     node *cur=root;
  26.     for(int i=0;str[i];i++){
  27.         int id=str[i]-'0';
  28.         cur=cur->next[id];
  29.     }
  30.     if(cur->cnt_trees>1) return true;   //inconsistent
  31.     for(int i=0;i<10;i++){
  32.         if(cur->next[i]!=NULL) return true; //inconsistent
  33.     }
  34.     return false;  //not yet inconsistent
  35. }
  36.  
  37. void del(node* cur)
  38. {
  39.     for(int i= 0;i<10;i++)
  40.         if (cur->next[i])
  41.             del(cur->next[i]);
  42.  
  43.     delete(cur);
  44. }
  45.  
  46. int main()
  47. {
  48.     int tc,cs=0;
  49.     string str;
  50.     scanf("%d",&tc);
  51.     while(tc--){
  52.         root=new node();
  53.         int n,f=1;
  54.         scanf("%d",&n);
  55.         vector<string>v;
  56.         getchar();
  57.         while(n--){
  58.             cin>>str;
  59.             insert_into_Trie(str);
  60.             v.push_back(str);
  61.         }
  62.         cout<<"Case "<<++cs<<": ";
  63.         for(int i=0;i<v.size();i++){
  64.             if(search(v[i])){
  65.                 cout<<"NO"<<endl;f=0;break;
  66.             }
  67.         }
  68.         if(f) cout<<"YES"<<endl;
  69.         del(root);
  70.     }
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
stdout
copy 
Case 1: NO
Case 2: YES
https://ideone.com/ro93Rq
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!