fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5.  
  6. #define NMAX 520100
  7. #define NODE_LOGMAX 20
  8.  
  9. //#define SOL_TRIVIAL // construieste efectiv fiecare arr (prin copiere) ; raspunde in O(1) la fiecare query
  10. //#define SOL_M // O(1) pentru fiecare concatenare ; O(M) pentru fiecare query; memorie: O(M)//
  11. #define SOL_LOGM_LOGLMAX_1 // O(1) pentru fiecare concatenare ; O(log(M)*log(LMAX)) pentru fiecare query; memorie: O(M*log(M)) (preprocesari de stramosi)
  12. //#define SOL_LOGM_LOGLMAX_2 // O(1) pentru fiecare concatenare ; O(log(M)*log(LMAX)) pentru fiecare query; memorie: O(M)
  13.  
  14. #define max(u,v) ((u) >= (v) ? (u) : (v))
  15.  
  16. int i, a, b, c, N, M, Q;
  17. int val[NMAX], left[NMAX], right[NMAX], h[NMAX];
  18. long long len[NMAX], psum[NMAX], p, sum;
  19.  
  20. #ifdef SOL_TRIVIAL
  21. int *arr[NMAX];
  22.  
  23. void solTrivial()
  24. {
  25. 	// answer the queries
  26. 	for (i = 1; i <= Q; i++)
  27. 	{
  28. 		scanf("%d %lld", &a, &p);
  29. 		printf("%d\n", arr[a][p - 1]);
  30. 	}
  31. }
  32. #endif
  33.  
  34. #ifdef SOL_M
  35. void solM()
  36. {
  37. 	// answer the queries
  38. 	for (i = 1; i <= Q; i++)
  39. 	{
  40. 		scanf("%d %lld", &a, &p);
  41.  
  42. 		while (len[a] > 1)
  43. 		{
  44. 			if (p > len[left[a]])
  45. 			{
  46. 				p -= len[left[a]];
  47. 				a = right[a];
  48. 			}
  49. 			else
  50. 				a = left[a];
  51. 		}
  52.  
  53. 		printf("%d\n", val[a]);
  54. 	}
  55. }
  56. #endif
  57.  
  58. #ifdef SOL_LOGM_LOGLMAX_1
  59. int anc[NODE_LOGMAX][NMAX];
  60.  
  61. void solLogMLogLMAX1()
  62. {
  63. 	// compute the anc values
  64. 	for (i = N + 1; i <= N + M; i++)
  65. 	{
  66. 		if (len[left[i]] >= len[right[i]])
  67. 			anc[0][i] = left[i];
  68. 		else
  69. 			anc[0][i] = right[i];
  70. 	}
  71.  
  72. 	for (a = 1; a < NODE_LOGMAX; a++)
  73. 		for (i = N + 1; i <= N + M; i++)
  74. 			anc[a][i] = anc[a - 1][anc[a - 1][i]];
  75.  
  76. 	// compute the psum values
  77. 	for (i = N + 1; i <= N + M; i++)
  78. 		if (anc[0][i] == left[i])
  79. 			psum[i] = psum[anc[0][i]];
  80. 		else
  81. 			psum[i] = psum[anc[0][i]] + len[left[i]];
  82.  
  83. 	// answer the queries
  84. 	for (i = 1; i <= Q; i++)
  85. 	{
  86. 		scanf("%d %lld", &a, &p);
  87.  
  88. 		while (len[a] > 1)
  89. 		{
  90. 			b = NODE_LOGMAX - 1;
  91. 			while (!anc[b][a])
  92. 				b--;
  93.  
  94. 			while (b >= 0)
  95. 			{
  96. 				sum = psum[a] - psum[anc[b][a]];
  97. 				if (p - sum >= 1 && p - sum <= len[anc[b][a]])
  98. 				{
  99. 					p -= sum;
  100. 					a = anc[b][a];
  101. 				}
  102.  
  103. 				b--;
  104. 			}
  105.  
  106. 			if (len[a] > 1)
  107. 			{
  108. 				if (p > len[left[a]])
  109. 				{
  110. 					p -= len[left[a]];
  111. 					a = right[a];
  112. 				}
  113. 				else
  114. 					a = left[a];
  115. 			}
  116. 		}
  117.  
  118. 		printf("%d\n", val[a]);
  119. 	}
  120. }
  121. #endif
  122.  
  123. #ifdef SOL_LOGM_LOGLMAX_2
  124. int parent[NMAX], cnt[NMAX], maxSonCnt[NMAX], maxSon[NMAX], pathLen[NMAX], pathRoot[NMAX];
  125. int bit[NMAX];
  126. int *path[NMAX];
  127.  
  128. void solLogMLogLMAX2()
  129. {
  130. 	// compute the parent values
  131. 	for (i = N + 1; i <= N + M; i++)
  132. 	{
  133. 		if (len[left[i]] >= len[right[i]])
  134. 			parent[i] = left[i];
  135. 		else
  136. 			parent[i] = right[i];
  137. 	}
  138.  
  139. 	for (i = N + M; i > N; i--)
  140. 	{
  141. 		cnt[i]++;
  142. 		pathLen[i]++;
  143.  
  144. 		cnt[parent[i]] += cnt[i];
  145.  
  146. 		if (cnt[i] > maxSonCnt[parent[i]])
  147. 		{
  148. 			maxSonCnt[parent[i]] = cnt[i];
  149. 			maxSon[parent[i]] = i;
  150. 			pathLen[parent[i]] = pathLen[i];
  151. 		}
  152. 	}
  153.  
  154. 	for (i = 1; i <= N; i++)
  155. 	{
  156. 		cnt[i]++;
  157. 		pathLen[i]++;
  158. 	}
  159.  
  160. 	for (i = 1; i <= N + M; i++)
  161. 		if (len[i] == 1 || i != maxSon[parent[i]])
  162. 		{
  163. 			path[i] = (int*) malloc(pathLen[i] * sizeof(int));
  164. 			path[i][pathLen[i] - 1] = i;
  165. 			pathRoot[i] = i;
  166. 		}
  167. 		else
  168. 		{
  169. 			path[i] = NULL;
  170. 			pathRoot[i] = pathRoot[parent[i]];
  171. 			path[pathRoot[i]][pathLen[i] - 1] = i;	
  172. 		}
  173.  
  174. 	// compute the psum values
  175. 	for (i = N + 1; i <= N + M; i++)
  176. 		if (parent[i] == left[i])
  177. 			psum[i] = psum[parent[i]];
  178. 		else
  179. 			psum[i] = psum[parent[i]] + len[left[i]];
  180.  
  181.  
  182. 	// compute the powers of two
  183. 	bit[0] = 1;
  184. 	for (i = 1; i < NODE_LOGMAX; i++)
  185. 		bit[i] = bit[i - 1] * 2;
  186.  
  187. 	// answer the queries
  188. 	for (i = 1; i <= Q; i++)
  189. 	{
  190. 		scanf("%d %lld", &a, &p);
  191.  
  192. 		while (len[a] > 1)
  193. 		{
  194. 			if (a == pathRoot[a])
  195. 			{
  196. 				if (p > len[left[a]])
  197. 				{
  198. 					p -= len[left[a]];
  199. 					a = right[a];
  200. 				}
  201. 				else
  202. 					a = left[a];
  203. 			}
  204. 			else
  205. 			{
  206. 				sum = psum[a] - psum[pathRoot[a]];
  207.  
  208. 				if (p - sum >= 1 && p - sum <= len[pathRoot[a]])
  209. 				{
  210. 					p -= sum;
  211. 					a = pathRoot[a];
  212. 				}
  213. 				else
  214. 				{
  215. 					b = NODE_LOGMAX - 1;
  216.  
  217. 					while (b >= 0)
  218. 					{
  219. 						if (pathLen[a] - 1 + bit[b] < pathLen[pathRoot[a]])
  220. 						{
  221. 							c = path[pathRoot[a]][pathLen[a] - 1 + bit[b]];
  222. 							sum = psum[a] - psum[c];
  223. 							if (p - sum >= 1 && p - sum <= len[c])
  224. 							{
  225. 								p -= sum;
  226. 								a = c;
  227. 							}
  228. 						}
  229.  
  230. 						b--;
  231. 					}
  232.  
  233. 					if (len[a] > 1)
  234. 					{
  235. 						if (p > len[left[a]])
  236. 						{
  237. 							p -= len[left[a]];
  238. 							a = right[a];
  239. 						}
  240. 						else
  241. 							a = left[a];
  242. 					}
  243.  
  244. 				}
  245. 			}
  246. 		}
  247.  
  248. 		printf("%d\n", val[a]);
  249.  
  250. 		//fprintf(stderr, "%d done\n", i);
  251. 	}
  252. }
  253. #endif
  254.  
  255. void solve()
  256. {
  257. 	freopen("carray.in", "r", stdin);
  258. 	freopen("carray.out", "w", stdout);
  259.  
  260. 	scanf("%d %d %d", &N, &M, &Q);
  261.  
  262. 	for (i = 1; i <= N; i++)
  263. 	{
  264. 		scanf("%d", &val[i]);
  265. 		len[i] = 1;
  266.  
  267. 		#ifdef SOL_TRIVIAL
  268. 			arr[i] = (int*) malloc(sizeof(int));
  269. 			arr[i][0] = val[i];
  270. 		#else
  271. 			left[i] = right[i] = h[i] = 0;
  272. 		#endif
  273. 	}
  274.  
  275. 	for (i = N + 1; i <= N + M; i++)
  276. 	{
  277. 		scanf("%d %d", &a, &b);
  278. 		len[i] = len[a] + len[b];
  279.  
  280. 		#ifdef SOL_TRIVIAL
  281. 			arr[i] = (int*) malloc(len[i] * sizeof(int));
  282. 			memcpy(&arr[i][0], &arr[a][0], len[a] * sizeof(int));
  283. 			memcpy(&arr[i][len[a]], &arr[b][0], len[b] * sizeof(int));
  284. 		#else
  285. 			left[i] = a;
  286. 			right[i] = b;
  287. 			h[i] = 1 + max(h[a], h[b]);
  288. 		#endif
  289. 	}
  290.  
  291.  
  292. 	#ifdef SOL_TRIVIAL
  293. 		solTrivial();
  294. 	#endif
  295.  
  296. 	#ifdef SOL_M
  297. 		solM();
  298. 	#endif
  299.  
  300. 	#ifdef SOL_LOGM_LOGLMAX_1
  301. 		solLogMLogLMAX1();
  302. 	#endif
  303.  
  304. 	#ifdef SOL_LOGM_LOGLMAX_2
  305. 		solLogMLogLMAX2();
  306. 	#endif
  307. }
  308.  
  309. int main()
  310. {
  311. 	int tstart = clock();
  312. 	solve();
  313.  
  314. 	fprintf(stderr, "Duration = %.3lf sec\n", ((double) (clock() - tstart)) / CLOCKS_PER_SEC);
  315.  
  316. 	return 0;
  317. }
Success #stdin #stdout #stderr 0s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Duration = 0.001 sec
https://ideone.com/TuWTe7
language:
C++14 (gcc 8.3)
created:
2 hours 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!