BotByte

Untitled

Mar 14th, 2018
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.21 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define MAX 100005
  6. int trie[MAX][10];
  7. int sz = 0;
  8. int end_here[MAX];
  9.  
  10. void add(string s)
  11. {
  12. int v = 0;
  13. for(int i=0; i<s.length(); i++){
  14. int x = s[i] - '0';
  15. if(trie[v][x] == -1) trie[v][x] = ++sz;
  16. v = trie[v][x];
  17. }
  18. end_here[v]++;
  19. }
  20.  
  21. bool search(string s)
  22. {
  23. int v = 0;
  24. for(int i=0; i<s.length(); i++){
  25. int x = s[i] - '0';
  26. if(trie[v][x] == -1) return false;
  27. v = trie[v][x];
  28. if(end_here[v]) return true;
  29. }
  30. return true;
  31. }
  32.  
  33. int main()
  34. {
  35. //freopen("in.txt", "r", stdin);
  36. //freopen("out.txt", "w", stdout);
  37. int cases;
  38. scanf("%d", &cases);
  39. int caseno = 0;
  40. while(cases--){
  41. memset(trie, -1, sizeof trie);
  42. memset(end_here, 0, sizeof end_here);
  43. sz = 0;
  44. int n;
  45. scanf("%d", &n);
  46. bool flag = true;
  47. for(int i=0; i<n; i++){
  48. string str;
  49. cin >> str;
  50. if(search(str)){
  51. flag = false;
  52. }
  53. add(str);
  54. }
  55. if(flag) printf("Case %d: YES\n", ++caseno);
  56. else printf("Case %d: NO\n", ++caseno);
  57. }
  58. }
Advertisement
Add Comment
Please, Sign In to add comment