fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int Long;
  4. //typedef long long int ll;
  5. typedef int ll;
  6. typedef ll ft;
  7. typedef set<int> si;
  8. typedef long long Long;
  9. typedef vector<int> vi;
  10. typedef vector<vi> vii;
  11. typedef vector<Long>vl;
  12. typedef pair<int,int>pii;
  13. typedef pair<Long,Long>pll;
  14. typedef pair<string,int>psi;
  15. typedef pair<double,double>pdd;
  16. #define get getchar_unlocked
  17. #define put putchar_unlocked
  18. #define pb push_back
  19. #define mp make_pair
  20. #define ff first
  21. #define ss second
  22. #define sz size()
  23. #define ln length()
  24. #define repstl(i, s) for (__typeof((s).end())i=(s).begin();i!=(s).end();++i)
  25. #define debug1(s,a) cout << s << " " << a << " " << endl;
  26. #define debug2(s,a,b) cout << s << " " << a << " " << b << " " << endl
  27. #define debug3(s,a,b,c) cout << s << " " << a << " " << b << " " << c << " " << endl;
  28. #define debug4(s,a,b,c,d) cout << s << " " << a << " " << b << " " << c << " " << d << " " << endl;
  29. #define debug5(s,a,b,c,d,e) cout << s << " " << a << " " << b << " " << c << " " << d << " " << e << " " << endl;
  30. #define PI 3.1415926535897932384626433832795
  31. #define FO freopen ("out.txt", "w", stdout)
  32. #define FI freopen ("in.txt", "r", stdin)
  33. #define ref(i,a,n) for(int i=a;i<=n;i++)
  34. #define reb(i,n,a) for(int i=n;i>=a;i--)
  35. #define rep(i,n) for(int i=0;i<n;i++)
  36. #define all(a) a.begin(),a.end()
  37. #define gi(n) scanf("%d",&n)
  38. #define gii(n) scanf("%lld",&n)
  39. #define gc(c) scanf(" %c",&c)
  40. #define gs(s) scanf(" %s",s);
  41. #define pi(n) printf("%d",n)
  42. #define pii(n) printf("%lld",n)
  43. #define pc(c) printf("%c",c)
  44. #define ps printf(" ")
  45. #define pn printf("\n")
  46. #define pl(a) printf("%s",a)
  47. #define l(a) 2*a+1
  48. #define r(a) 2*a+2
  49. #define left(a,b) a,(a+b)/2
  50. #define right(a,b) (a+b)/2+1,b
  51. #define mid(a,b) (a+b)/2
  52. void gl(char *str){register char c=0;register int i=0;while(c<33)c=get();while(c!='\n'){str[i]=c;c=get();i=i+1;}str[i]='\0';}
  53. void gfi(ft &x) {register ft c = get(); x = 0; ft sn=1;for(;(c<48 || c>57);c = get()) if(c=='-') sn=-1;for(;c>47 && c<58;c = get()) {x = (x<<1) + (x<<3) + c - 48;}x*=sn;}
  54. //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  55. //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  56. //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  57. //int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction
  58.  
  59. string s[26]={"01","1000","1010","100","0","0010","110","0000","00","0111","101","0100","11","10","111","0110","1101","010","000","1","001","0001","011","1001","1011","1100"};
  60.  
  61. struct node { ll val; struct node *l,*r; };
  62. typedef struct node nod;
  63.  
  64. nod *create() {
  65. 	nod *tem=(nod *) malloc (sizeof(nod));
  66. 	tem->l=tem->r=NULL;
  67. 	tem->val=0;
  68. 	return tem;
  69. }
  70.  
  71. #define N 100000
  72. string str,temp;
  73. ll l1,l2,dp[N];
  74.  
  75. void trie(nod *head,ll ind) {
  76. 	if(ind==l2) {
  77. 		head->val=1;
  78. 		return ;
  79. 	}
  80. 	nod *tem=create();
  81. 	if(temp[ind]=='0') {
  82. 		if(head->l==NULL) head->l=tem;
  83. 		trie(head->l,ind+1);
  84. 	} else {
  85. 		if(head->r==NULL) head->r=tem;
  86. 		trie(head->r,ind+1);
  87. 	}
  88. }
  89.  
  90. ll go(nod *Head,nod *head,ll ind) {
  91. 	if(ind==l1) {
  92. 		if(head->val==1) return 1; else return 0;
  93. 	}
  94. 	ll ans=0;	
  95. 	if(str[ind]=='.') {
  96. 		ans=head->l==NULL?ans:ans+go(Head,head->l,ind+1);
  97. 	} else {
  98. 		ans=head->r==NULL?ans:ans+go(Head,head->r,ind+1);
  99. 	}
  100. 	if(head->val==1) {
  101. 		if(dp[ind]!=-1) return dp[ind];
  102. 		ans=ans+go(Head,Head,ind);
  103. 		return dp[ind]=ans;
  104. 	}
  105. 	return ans;
  106. }
  107.  
  108. void solve() {
  109. 	cin >> str;
  110. 	l1=str.ln;
  111. 	ll n;
  112. 	gfi(n);
  113. 	nod *head;
  114. 	head=create();
  115. 	rep(i,n) {
  116. 		string temp1;
  117. 		cin >> temp1;
  118. 		ll l=temp1.ln;
  119. 		temp="";
  120. 		rep(i,l) temp+=s[temp1[i]-'A'];
  121. 		l2=temp.ln;
  122. 		trie(head,0);
  123. 	}
  124. 	rep(i,l1+1) dp[i]=-1;
  125. 	pi(go(head,head,0));pn;
  126. }
  127.  
  128. int main() {
  129. 	ll t;
  130. 	gfi(t);
  131. 	while(t--) {
  132. 		solve();
  133. 	}	
  134. 	return 0;
  135. }
  136.  
Time limit exceeded #stdin #stdout 5s 3664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eBbe5o
language:
C++ (gcc 8.3)
created:
8 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!