fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5. template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
  6. template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
  7. const int MAXN = (1 << 20);
  8.  
  9. struct suffix_automaton
  10. {
  11. 	map<char, int> to[MAXN];
  12. 	int len[MAXN], link[MAXN];
  13. 	int last, psz = 0;
  14.  
  15. 	void add_letter(char c)
  16. 	{
  17. 		int p = last, cl, q;
  18. 		if(to[p].count(c))
  19. 		{
  20.   			q = to[p][c];
  21. 			if(len[q] == len[p] + 1)
  22. 			{
  23. 				last = q;
  24. 				return;
  25. 			}
  26.  
  27. 			cl = psz++;
  28. 			len[cl] = len[p] + 1;
  29. 			to[cl] = to[q];
  30. 			link[cl] = link[q];
  31. 			link[q] = cl;
  32. 			last = cl;
  33.  
  34. 			for(; to[p][c] == q; p = link[p])
  35. 				to[p][c] = cl;
  36.  
  37. 			return;
  38. 		}
  39.  
  40. 		last = psz++;
  41. 		len[last] = len[p] + 1;
  42.  
  43. 		for(; to[p][c] == 0; p = link[p])
  44. 			to[p][c] = last;
  45.  
  46. 		if(to[p][c] == last) 
  47. 		{
  48. 			link[last] = p;
  49. 			return;
  50. 		}
  51.  
  52. 		q = to[p][c];
  53. 		if(len[q] == len[p] + 1)
  54. 		{
  55. 			link[last] = q;
  56. 			return;
  57. 		}
  58.  
  59. 		cl = psz++;
  60. 		len[cl] = len[p] + 1;
  61. 		to[cl] = to[q];
  62. 		link[cl] = link[q];
  63. 		link[q] = cl;
  64. 		link[last] = cl;
  65.  
  66. 		for(; to[p][c] == q; p = link[p])
  67. 			to[p][c] = cl;
  68. 	}
  69.  
  70. 	void clear()
  71. 	{
  72. 		for(int i = 0; i < psz; i++)
  73. 			len[i] = 0, link[i] = 0, to[i].clear();
  74. 		psz = 1;
  75. 		last = 0;
  76. 	}
  77.  
  78. 	void init(string s)
  79. 	{
  80. 		clear();
  81. 		for(int i = 0; i < (int)s.size(); i++)
  82. 			add_letter(s[i]);
  83. 	}
  84.  
  85. 	suffix_automaton() { memset(link, 0, sizeof(link)); memset(len, 0, sizeof(len)); clear();}
  86. };
  87.  
  88. int n;
  89. vector<int> G[MAXN];
  90. string s[MAXN];
  91.  
  92. void read()
  93. {
  94. 	cin >> n;
  95. 	for(int i = 2; i <= n; i++)
  96. 	{
  97. 		int p;
  98. 		cin >> p;
  99. 		G[p].push_back(i);
  100. 	}
  101.  
  102. 	for(int i = 1; i <= n; i++)
  103. 		cin >> s[i];
  104. }
  105.  
  106. int tr_sz[MAXN];
  107. suffix_automaton sa;
  108. int answer = -1;
  109.  
  110. void pre_dfs(int u, int pr)
  111. {
  112. 	tr_sz[u] = s[u].size();
  113. 	for(int v: G[u])
  114. 		if(v != pr)
  115. 		{
  116. 			pre_dfs(v, u);
  117. 			tr_sz[u] += tr_sz[v];
  118. 		}
  119. }
  120.  
  121. void add_vertex(int u)
  122. {
  123. 	sa.last = 0;
  124. 	for(auto it: s[u])
  125. 		sa.add_letter(it);
  126. }
  127.  
  128. void check_vertex(int u)
  129. {
  130. 	int x = 0, l = 0;
  131. 	for(auto c: s[u])
  132. 	{
  133. 		while(x != 0 && !sa.to[x].count(c)) x = sa.link[x], l = sa.len[x];
  134. 		if(sa.to[x].count(c)) l++, x = sa.to[x][c];
  135. 		chkmax(answer, l);
  136. 	}
  137. }
  138.  
  139. void add(int u, int pr)
  140. {
  141. 	add_vertex(u);
  142. 	for(int v: G[u])
  143. 		if(v != pr)
  144. 			add(v, u);
  145. }
  146.  
  147. void check(int u, int pr)
  148. {
  149. 	check_vertex(u);
  150. 	for(int v: G[u])
  151. 		if(v != pr)
  152. 			check(v, u);
  153. }
  154.  
  155. void dfs(int u, int pr, int keep)
  156. {
  157. 	pair<int, int> mx = {-1, -1};
  158. 	for(int v: G[u])
  159. 		if(v != pr)
  160. 			mx = max(mx, {tr_sz[v], v});
  161.  
  162. 	for(int v: G[u])
  163. 		if(v != pr && v != mx.second)
  164. 			dfs(v, u, 0);
  165.  
  166. 	if(mx.second != -1)
  167. 		dfs(mx.second, u, 1);
  168.  
  169. 	for(int v: G[u])
  170. 		if(v != pr && v != mx.second)
  171. 		{
  172. 			check(v, u);
  173. 			add(v, u);
  174. 		}
  175.  
  176. 	add_vertex(u);
  177.  
  178. 	if(keep) return;
  179. 	sa.clear();
  180. }
  181.  
  182. void solve()
  183. {
  184. 	sa.clear();
  185. 	pre_dfs(1, -1);
  186. 	dfs(1, -1, 1);
  187. 	cout << answer << endl;
  188. }
  189.  
  190. int main()
  191. {
  192. 	ios_base::sync_with_stdio(false);
  193. 	cin.tie(NULL);
  194.  
  195. 	read();
  196. 	solve();
  197. 	return 0;
  198. }
Success #stdin #stdout 0.06s 117760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/gIoH2L
language:
C++ (gcc 8.3)
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!