fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef int ll;
  4. typedef long double ld;
  5.  
  6. #define lp(var,start,end) for (ll var = start; var <end ; ++var)
  7. #define rlp(var,start,end) for(ll var = start; var>=end ; var--)
  8. #define pb push_back
  9. #define mp make_pair
  10. #define pf push_front
  11. #define ff first
  12. #define ss second
  13. #define vll vector<ll>
  14. #define vld vector<ld>
  15. #define pll pair<ll,ll> 
  16. #define pld pair<ld,ld> 
  17. #define vpll vector<pll>
  18. #define vpld vector<pld>
  19. #define all(X) X.begin(),X.end()
  20. #define endl "\n"
  21. #define sz(x) ((int)(x).size())
  22. const ll N=1e6+5,inf=1e9,k=27;
  23. ll dp[N],ans;
  24. struct node{
  25. 	ll nxt[k],go[k];
  26. 	ll p,link,nxtleaf;
  27. 	ll cnt;
  28. 	ll pch;
  29. 	ll leaf;
  30. 	ll len;
  31. };
  32.  
  33. node init()
  34. {
  35. 	node tp;
  36. 	lp(i,0,k)
  37. 	{
  38. 		tp.nxt[i]=-1;
  39. 		tp.go[i]=-1;
  40. 	}
  41. 	tp.nxtleaf=0;
  42. 	tp.link=-1;
  43. 	tp.leaf=0;
  44. 	tp.cnt=0;
  45. 	return tp;
  46. }
  47.  
  48. vector<node> v;
  49.  
  50. void insert(string s)
  51. {
  52. 	ll cur=0;
  53. 	lp(i,0,sz(s))
  54. 	{
  55. 		v[cur].cnt++;
  56. 		ll a=s[i]-'a';
  57. 		if(v[cur].nxt[a]==-1)
  58. 		{
  59. 			node tp = init();
  60. 			tp.p=cur;
  61. 			tp.pch=a;
  62. 			v.pb(tp);
  63. 			v[cur].nxt[a]=sz(v)-1;
  64. 		}
  65. 		v[cur].len=i;
  66. 		cur=v[cur].nxt[a];
  67. 	}
  68. 	v[cur].len=sz(s);
  69. 	v[cur].cnt++;	
  70. 	v[cur].leaf=1;
  71. }
  72.  
  73. ll go(ll cur, ll c);
  74.  
  75. ll get_link(ll cur)
  76. {
  77. 	if(v[cur].link==-1)
  78. 	{
  79. 		if(cur==0 || v[cur].p==0 )
  80. 		{
  81. 			v[cur].link = 0;
  82. 		}
  83. 		else
  84. 		{
  85. 			v[cur].link =  go(get_link(v[cur].p),v[cur].pch);
  86. 		}
  87.  
  88. 	}
  89.  
  90. 	return v[cur].link;
  91. }
  92.  
  93. ll go(ll cur, ll c)
  94. {
  95. 	if(v[cur].go[c]==-1)
  96. 	{
  97. 		if(v[cur].nxt[c]!=-1)
  98. 		{
  99. 			v[cur].go[c]=v[cur].nxt[c];
  100. 		}
  101. 		else
  102. 		{
  103. 			v[cur].go[c] = cur == 0 ? 0 : go(get_link(cur), c);
  104. 		}
  105. 	}
  106. 	return v[cur].go[c];
  107. }
  108.  
  109.  
  110. ll bfs()
  111. {
  112. 	ll cur=0;
  113. 	queue<ll> q;
  114. 	q.push(cur);
  115. 	while(!q.empty())
  116. 	{
  117. 		cur=q.front();
  118. 		q.pop();
  119. 		get_link(cur);
  120. 		lp(i,0,k)
  121. 		{
  122. 			if(v[cur].nxt[i]>0)
  123. 			{
  124. 				q.push(v[cur].nxt[i]);
  125. 			}	
  126. 		}
  127. 	}
  128. 	return 0;
  129. }
  130.  
  131. ll chk(ll cur,ll val)
  132. {
  133. 	if(cur==0)return 0;
  134.  
  135. 	if(dp[cur]==-1)
  136. 	{
  137. 		dp[cur]=v[cur].len*v[cur].cnt;
  138. 		dp[cur]=max(dp[cur],chk(v[cur].link,val));
  139. 	}
  140. 	ans=max(ans,dp[cur]*val);
  141. 	return dp[cur];
  142. }
  143.  
  144. int main()
  145. {
  146. 	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  147. 	freopen("exciting.in", "r", stdin);
  148. 	ll t;
  149. 	cin >> t;
  150. 	while(t--)
  151. 	{
  152. 		ans=0;
  153. 		v.clear();
  154. 		ll n;
  155. 		cin >> n;
  156. 		// if(n<=0)
  157. 		// {
  158. 			// while(1);
  159. 		// }
  160. 		// assert(n>0);
  161. 		string s[n];
  162. 		node root =init();
  163. 		v.pb(root);
  164. 		vector<ll> a[n];
  165. 		lp(i,0,n)
  166. 		{
  167. 			cin >> s[i];
  168. 			insert(s[i]);
  169. 		}
  170. 		lp(i,0,n)
  171. 		{
  172. 			lp(j,0,sz(s[i]))
  173. 			{
  174. 				ll x;
  175. 				cin >> x;
  176. 				a[i].pb(x);
  177. 			}
  178. 		}
  179. 		lp(i,0,sz(v)+2)
  180. 		{
  181. 			dp[i]=-1;
  182. 		}
  183. 		bfs();
  184. 		ll cur=0;
  185. 		lp(i,0,n)
  186. 		{
  187. 			cur=0;
  188. 			lp(j,0,sz(s[i]))
  189. 			{
  190. 				cur=go(cur,s[i][j]-'a');
  191. 				chk(cur,a[i][j]);
  192. 			}
  193. 		}
  194. 		cout<<ans<<endl;
  195. 	}
  196. 	return 0;	
  197. }
Success #stdin #stdout 0s 4540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Xj7jgc
language:
C++14 (gcc 8.3)
created:
5 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!