Advertisement
Guest User

Untitled

a guest
Jan 6th, 2016
255
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.77 KB | None | 0 0
  1. #define filer() freopen("in.txt","r",stdin)
  2. #define filew() freopen("out.txt","w",stdout)
  3.  
  4. #include<iostream>
  5. #include<stdio.h>
  6. #include<string.h>
  7. #include<math.h>
  8. #include<algorithm>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #include <map>
  13. #define INF 1<<29
  14. #define SET(a, x) memset((a), (x), sizeof(a))
  15. #define i64 long long
  16. #define pb push_back
  17. #define EPS 1e-9
  18. using namespace std;
  19.  
  20. struct node
  21. {
  22. bool endmark;
  23. node *next[10+1];
  24. node()
  25. {
  26. endmark=false;
  27. for(int i=0;i<10;i++) next[i]=NULL;
  28. }
  29. }*root;
  30.  
  31. void insert(char *str,int len)
  32. {
  33. node *curr=root;
  34. for(int i=0;i<len;i++)
  35. {
  36. int id=str[i]-'0';
  37. if(curr->next[id]==NULL)
  38. curr->next[id]=new node();
  39. curr=curr->next[id];
  40. }
  41. curr->endmark=1;
  42.  
  43. }
  44. bool search(char *str,int len)
  45. {
  46. node *curr=root;
  47. for(int i=0;i<len;i++)
  48. {
  49. int id=str[i]-'0';
  50. //if(curr->next[id]==NULL) return false;
  51. curr=curr->next[id];
  52. }
  53. for(int id=0;id<10;id++)
  54. {
  55. if(curr->next[id]!=NULL)return false;
  56. }
  57. return true;
  58. }
  59.  
  60.  
  61.  
  62. void del(node *cur)
  63. {
  64. for(int i=0;i<10;i++)
  65. if(cur->next[i])
  66. del(cur->next[i]) ;
  67. delete(cur) ;
  68. }
  69.  
  70.  
  71.  
  72. char S[10009][12];
  73.  
  74. int main()
  75. {
  76. //filer();
  77. int i,j,k ,T,cas=0;
  78. //scanf("%d%d",,&N,&T);
  79. scanf("%d",&T);
  80. int n;
  81.  
  82. while(T--)
  83. {
  84. root=new node();
  85. scanf("%d",&n);
  86. for(i=0;i<n;i++)
  87. {
  88. scanf("%s",S[i]);
  89. insert(S[i],strlen(S[i]));
  90. }
  91. bool t=1;
  92. for(i=0;i<n;i++)
  93. {
  94. t=search(S[i],strlen(S[i]));
  95. if(!t)break;
  96. }
  97. if(!t)printf("Case %d: NO\n",++cas);
  98. else printf("Case %d: YES\n",++cas);
  99. del(root);
  100. }
  101.  
  102.  
  103. return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement