fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb(a) push_back(a)
  4. #define mp(a,b) make_pair(a,b)
  5. #define ll long long
  6. #define pii pair<int,int>
  7. #define pll pair<ll,ll>
  8. #define forr(a,b,c) for(int a=b;a<c;a++)
  9. #define forrev(a,b,c) for(int a=b;a>c;a--)
  10. #define all(v) v.begin(),v.end()
  11. #define revall(v) v.rbegin(),v.rend()
  12. #define allk(v,k) v.begin()+k,v.end()
  13. #define revallk(v,k) v.rbegin()+k,v.rend()
  14. #define allkj(v,k,j) v.begin()+k,v.end()-j
  15. #define revallkj(v,k,j) v.rbegin()+j,v.rend()-k
  16. #define ff first
  17. #define ss second
  18. ////////////////////////// non-modifiable /////////////////////////////////
  19.  
  20. #define mod 1000000007
  21. #define eps 1e-9
  22. #define inf INT_MAX
  23. #define infl LONG_LONG_MAX
  24. ll power(ll a,ll n)
  25. {
  26. 	if(a==0)return 0;
  27. 	if(a==1 || n==0)return 1;
  28. 	if(n==1)return a%mod;//can remove mod?
  29. 	ll t=power(a,n/2);
  30. 	t=t*t%mod;
  31. 	if(n&1)return t*a%mod;
  32. 	return t;
  33. }
  34. #define P (int)(2e6)+9
  35. #define FACTORIZE 1
  36. #define DETERMINE 2
  37. /*int primes[P];
  38. void sieve(int prime=2)//2->detects prime, 1->max prime in factorization
  39. {
  40. 	forr(i,2,P-3)
  41. 	{
  42. 		if(!primes[i])
  43. 		for(int j=prime*i;j<P-3;j+=i)primes[j]=i;
  44. 	}
  45. 	//forr(i,1,21)cout<<primes[i]<<" ";cout<<endl;
  46. 	if(prime==2)
  47. 	{
  48. 		forr(i,1,P-3)
  49. 		{
  50. 			primes[i] = ( primes[i] == 0 );
  51. 		}
  52. 	}
  53. 	else
  54. 		primes[1] = 1;
  55. }*/
  56. int popcount(ll a)
  57. {
  58. 	int c=0;
  59. 	while(a)
  60. 	{
  61. 		c++;
  62. 		a-=a&-a;
  63. 	}
  64. 	return c;
  65. }
  66. void factorize(int a)
  67. {
  68.  
  69. }
  70. void update(int tree[],int idx,int val,int maxval)
  71. {
  72. 	for(;idx<=maxval;idx+=idx&-idx)
  73. 	{
  74. 		tree[idx]+=val;
  75. 		//tree[idx]%=mod;
  76. 	}
  77. }
  78. int read(int tree[],int idx)
  79. {
  80. 	ll sum=0;
  81. 	for(;idx>0;idx-=idx&-idx)
  82. 	{
  83. 		sum+=tree[idx];
  84. 		//sum%=mod;
  85. 	}
  86. 	return sum;
  87. }
  88. ////////////////////////// MODIFIABLE /////////////////////////////////////
  89.  
  90. struct node2
  91. {
  92. 	int id,val;
  93. 	node2()
  94. 	{
  95. 		static int ctx=1;
  96. 		id=ctx++;
  97. 	};
  98. 	node2(int a,int b=0,int c=0,int d=0,int e=0,int f=0)
  99. 	{
  100. 		val=a;
  101. 	}
  102. };
  103. struct comp2
  104. {
  105. 	bool operator()(int a,int b)
  106. 	{
  107. 		//return a<b;
  108. 		return b<a;	//min heap	
  109. 	}
  110. };
  111. bool cmp2(int a,int b)
  112. {
  113. 	//return a<b;
  114. 	return b<a;
  115. }
  116.  
  117. struct node
  118. {
  119. 	bool present;
  120. 	node * child[26];
  121. 	node()
  122. 	{
  123.  
  124. 	};
  125. 	node(int a,int b=0,int c=0,int d=0,int e=0,int f=0)
  126. 	{
  127. 		//val=a;
  128. 	}
  129. };
  130. struct comp
  131. {
  132. 	bool operator()(int a,int b)
  133. 	{
  134. 		//return a<b;
  135. 		return b<a;	//min heap	
  136. 	}
  137. };
  138. bool cmp(int a,int b)
  139. {
  140. 	//return a<b;
  141. 	return b<a;
  142. }
  143. ////////////////////////// custom-defined /////////////////////////////////
  144. #define N 500009
  145. int n,m,a,b,c,d,k,h,w,x,y,p,q,t,ans,res,ma,mi,T,act=0,pas=1,cur,flag,now;
  146. int len[N];
  147. string s[N];
  148.  
  149. node * root;
  150.  
  151. //vector<string> s;
  152. double e,f,z;
  153. vector<int> v[1], vec;
  154. set<int> sett;
  155. typedef map<int,int> Mapp;
  156. Mapp mapp;
  157. ////////////////////////// variable declarations //////////////////////////
  158.  
  159. void print()//for detailed output of [a data structure]
  160. {
  161.  
  162. }
  163. void print2()//for detailed output of [a data structure]
  164. {
  165.  
  166. }
  167. void input()
  168. {
  169. 	ios_base::sync_with_stdio(false);cin.tie(NULL);
  170. 	cin >> n;
  171. 	//scanf("%d",&n);
  172.  
  173. 	//cout << "n=" << n << endl;
  174.  
  175. 	forr(i,1,n+1) cin >> s[i];
  176. 		//scanf("%s",s[i]);
  177.  
  178. 	//forr(i,1,n+1) cout << s[i] << endl;
  179.  
  180. 	//cout << " lol " << endl;
  181. }
  182. node * insert( node * root, string& s, int idx, int length, int sid )
  183. {
  184. 	if( root -> present == 1 )
  185. 	{
  186. 		len[ sid ] = idx;
  187. 		return root;
  188. 	}
  189.  
  190. 	if( idx == length )
  191. 	{
  192. 		root -> present = 1;
  193. 		return root;
  194. 	}
  195.  
  196. 	forr(i,0,s[idx]-'a')
  197. 		if( root->child[i] != NULL )
  198. 		{
  199. 			len[ sid ] = idx;
  200. 			root -> present = 1;
  201. 			return root;
  202. 		}
  203.  
  204. 	//if( root->child[ s[idx] - 'a' ] != NULL &&  )
  205.  
  206. 	if( root->child[ s[idx] - 'a' ] == NULL )
  207. 		root->child[ s[idx] - 'a' ] = (node*) malloc( sizeof( node ) );
  208.  
  209. 	root->child[ s[idx] - 'a' ] = insert( root->child[ s[idx] - 'a' ], s, idx+1, length, sid );
  210.  
  211. 	return root;
  212.  
  213. }
  214. void solve()
  215. {
  216. 	forr(i,1,n+1) len[i] = s[i].length();
  217.  
  218. 	root = (node*) malloc( sizeof( node ) );
  219.  
  220. 	forrev(i,n,0)
  221. 	{
  222. 		root = insert( root, s[i], 1, len[i], i );
  223. 	}
  224. }
  225. void output()
  226. {
  227. 	char buffer[500009] = {0};
  228. 	int id = 0;
  229.  
  230. 	forr(i,1,n+1)
  231. 	{
  232. 		forr(j,0,len[i])
  233. 			buffer[id++] = s[i][j];
  234. 			//printf("%c",s[i][j]);
  235.  
  236. 		buffer[id++] = '\n';
  237. 		//printf("\n");
  238. 		//cout << string( s[i].begin(), s[i].begin() + len[i] ) << endl;
  239. 	}
  240.  
  241. 	//printf("%s\n",buffer);
  242.  
  243. 	buffer[ id-1 ] = 0;
  244.  
  245. 	cout << buffer;
  246. }
  247. ///////////////////////////// my functions ////////////////////////////////
  248.  
  249. int main() 
  250. {
  251. 	input();
  252. 	solve();
  253. 	output();
  254. 	return 0;
  255. }
  256. //// MAIN //// MAIN //// MAIN //// MAIN //// MAIN //// MAIN //// MAIN ////
Success #stdin #stdout 0.01s 33184KB
comments (?)
stdin
copy 
3
#book
#bigtown
#big
stdout
copy 
#b
#big
#big
https://ideone.com/Mxgyyt
language:
C++14 (gcc 8.3)
created:
7 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!