fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. typedef vector <int> vi;
  5. typedef vector <vi> vii;
  6. typedef pair<int,int> pii;
  7. typedef int ft;
  8. #define get getchar_unlocked
  9. #define put putchar_unlocked
  10. #define pb push_back
  11. #define mp make_pair
  12. #define ff first
  13. #define ss second
  14. #define sz size()
  15. #define ln length()
  16. #define rep(i,n) for(int i=0;i<n;i++)
  17. #define ref(i,a,n) for(int i=a;i<=n;i++)
  18. #define reb(i,n,a) for(int i=n;i>=a;i--)
  19. #define all(a) a.begin(),a.end()
  20. #define gi(n) scanf("%d",&n)
  21. #define gii(n) scanf("%lld",&n)
  22. #define gc(c) scanf(" %c",&c)
  23. #define pi(n) printf("%d",n)
  24. #define pii(n) printf("%lld",n)
  25. #define pc(c) printf("%c",c)
  26. #define ps printf(" ")
  27. #define pn printf("\n")
  28. void gl(char *str) { char c; int i=0; if((c=get())!='\n') str[i++]=c; while((c=get())!='\n') str[i++]=c;str[i]='\0'; }
  29. void pl(char *str) { rep(i,strlen(str)) put(str[i]); }
  30. void gfi(ft &x) {
  31. register ft c = get(); x = 0; ft sn=1;
  32. for(;(c<48 || c>57);c = get()) if(c=='-') sn=-1;
  33. for(;c>47 && c<58;c = get()) {x = (x<<1) + (x<<3) + c - 48;}
  34. x*=sn;
  35. }
  36.  
  37. struct node {
  38. 	int data;
  39. 	struct node *next[26];
  40. }*head;
  41.  
  42. typedef struct node node;
  43.  
  44. node *create() {
  45. 	node *temp;
  46. 	temp = (node*) malloc (sizeof(node));
  47. 	rep(i,26) temp->next[i]=NULL;
  48. 	return temp;
  49. }
  50.  
  51. char str[100000],temp[100000];
  52. int n,m,cnt=0,ans=0;
  53.  
  54. void Trie(node *ptr,int i) {
  55. 	if(i<n) {
  56. 		if(ptr->next[str[i]-'A']==NULL) {
  57. 			cnt++;
  58. 			ptr->next[str[i]-'A']=create();
  59. 			Trie(ptr->next[str[i]-'A'],i+1);
  60. 		} else {
  61. 			Trie(ptr->next[str[i]-'A'],i+1);
  62. 		}
  63. 	}
  64. }
  65.  
  66. void deallocate(node *ptr) {
  67. 	if(ptr!=NULL) {
  68. 		rep(i,26) {
  69. 			if(ptr->next[i]!=NULL) deallocate(ptr->next[i]);
  70. 		}
  71. 	free(ptr);
  72. 	}
  73. }
  74.  
  75. int main() {
  76. 	int t;
  77. 	gfi(t); //get fast input
  78. 	while(t--) {
  79. 		scanf("%s",temp);
  80. 		m=strlen(temp);
  81. 		deallocate(head); // deallocating all memory
  82. 		head=create();
  83. 		ans=0;
  84. 		rep(i,m) {
  85. 			int k=0;
  86. 			ref(j,i,m-1) {
  87. 				str[k++]=temp[j];		
  88. 			}
  89. 			str[k]='\0';
  90. 			n=strlen(str);
  91. 			cnt=0;
  92. 			Trie(head,0);
  93. 			ans+=cnt;
  94. 		}
  95. 		cout << ans << endl;
  96. 	}
  97. 	return 0;
  98. }
  99.  
Time limit exceeded #stdin #stdout 5s 3336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pM7OEP
language:
C++14 (gcc 8.3)
created:
9 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!