fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3.  
  4. struct node
  5. {
  6. 	struct node * parent;
  7. 	struct node * children[10]; //to indicate which number it is (0-9)
  8. 	bool isLeaf;
  9. };
  10.  
  11. bool Insert(struct node *trieTree, char number[])
  12. {
  13. 	int i=0;
  14. 	bool result = true;
  15.  
  16. 	struct node *temp = trieTree;
  17.  
  18. 	while(number[i] != '\0' )
  19. 	{
  20. 		//case 1: 911 comes after 9112
  21. 		//case 2: 9112 comes after 911
  22.  
  23. 		char n = number[i];
  24.  
  25. 		if(trieTree->children[n - '0'] == NULL)
  26. 		{
  27. 			struct node *q = new node();
  28. 			temp->children[n - '0'] = q;
  29. 			//= (struct node *) calloc(1,sizeof (struct node));
  30. 			temp->children[n-'0']->parent = temp;
  31. 			temp->children[n-'0']->isLeaf = false;
  32. 		}
  33.  
  34. 		temp = temp->children[n-'0'];
  35.  
  36. 		if(temp->isLeaf == true) //9112 comes after 911
  37. 		{
  38. 			result = false;
  39. 			return result;
  40. 		}
  41.  
  42. 		i++;
  43. 	}
  44.  
  45. 	//911 comes after 9112
  46. 	for(int j=0; j<9; j++)
  47. 	{
  48. 		if(temp->children[j] != NULL)
  49. 		{
  50. 			result = false;
  51. 			return result;
  52. 		}
  53. 	}
  54.  
  55. 	temp->isLeaf = true;
  56. 	return result;
  57. }
  58.  
  59. int main()
  60. {
  61. 	int T;
  62. 	scanf("%d",&T);
  63. 	while(T--)
  64. 	{
  65. 		int n;
  66. 		scanf("%d",&n);
  67.  
  68. 		struct node *trieTree = new node();
  69. 		// (struct node *) calloc(1,sizeof(struct node));
  70. 		char number[10];
  71. 		bool result = true;
  72.  
  73. 		for(int i=0; i<n; i++)
  74. 		{
  75. 			scanf("%s",number);	
  76.  
  77. 			if(!Insert(trieTree, number)) result = false;
  78. 		}
  79.  
  80. 		if(result) printf("YES\n");
  81. 		else printf("NO\n");
  82.  
  83. 		free(trieTree);
  84. 	}
  85. }
Runtime error #stdin #stdout 0s 2872KB
comments (?)
stdin
copy 
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
stdout
copy 
Standard output is empty
https://ideone.com/Y7mRRY
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 years ago
visibility:
secret

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!