fork download 
  1. //Tanuj Khattar
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef pair<int,int>   II;
  7. typedef vector< II >      VII;
  8. typedef vector<int>     VI;
  9. typedef vector< VI > 	VVI;
  10. typedef long long int 	LL;
  11.  
  12. #define PB push_back
  13. #define MP make_pair
  14. #define F first
  15. #define S second
  16. #define SZ(a) (int)(a.size())
  17. #define ALL(a) a.begin(),a.end()
  18. #define SET(a,b) memset(a,b,sizeof(a))
  19.  
  20. #define si(n) scanf("%d",&n)
  21. #define dout(n) printf("%d\n",n)
  22. #define sll(n) scanf("%lld",&n)
  23. #define lldout(n) printf("%lld\n",n)
  24. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  25.  
  26. #define TRACE
  27.  
  28. #ifdef TRACE
  29. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  30. template <typename Arg1>
  31. void __f(const char* name, Arg1&& arg1){
  32. 	cerr << name << " : " << arg1 << std::endl;
  33. }
  34. template <typename Arg1, typename... Args>
  35. void __f(const char* names, Arg1&& arg1, Args&&... args){
  36. 	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  37. }
  38. #else
  39. #define trace(...)
  40. #endif
  41.  
  42. //FILE *fin = freopen("in","r",stdin);
  43. //FILE *fout = freopen("out","w",stdout);
  44. typedef struct node{
  45. 	int val,prior,size;
  46. 	struct node *l,*r;
  47. }node;
  48. typedef node* pnode;
  49. int sz(pnode t){
  50. 	return t?t->size:0;
  51. }
  52. void upd_sz(pnode t){
  53. 	if(t)t->size = sz(t->l)+1+sz(t->r);
  54. }
  55. void split(pnode t,pnode &l,pnode &r,int key){
  56. 	if(!t)l=r=NULL;
  57. 	else if(t->val<=key)split(t->r,t->r,r,key),l=t;//elem=key comes in l
  58. 	else split(t->l,l,t->l,key),r=t;
  59. 	upd_sz(t);
  60. }
  61. void merge(pnode &t,pnode l,pnode r){
  62. 	if(!l || !r)t=l?l:r;
  63. 	else if(l->prior > r->prior)merge(l->r,l->r,r),t=l;
  64. 	else merge(r->l,l,r->l),t=r;
  65. 	upd_sz(t);
  66. }
  67. void insert(pnode &t,pnode it){
  68. 	if(!t) t=it;
  69. 	else if(it->prior>t->prior)split(t,it->l,it->r,it->val),t=it;
  70. 	else insert(t->val<it->val?t->r:t->l,it);
  71. 	upd_sz(t);
  72. }
  73. void erase(pnode &t,int key){
  74. 	if(!t)return;
  75. 	else if(t->val==key){pnode temp=t;merge(t,t->l,t->r);free(temp);}
  76. 	else erase(t->val<key?t->r:t->l,key);
  77. 	upd_sz(t);
  78. }
  79. pnode init(int val){
  80. 	pnode ret = (pnode)malloc(sizeof(node));
  81. 	ret->val=val;ret->size=1;ret->prior=rand();ret->l=ret->r=NULL;
  82. 	return ret;
  83. }
  84. const int INF = int(1e9);
  85. int kth(pnode t,int k)
  86. {
  87. 	if(!t)return INF;
  88. 	if(sz(t->l) == k-1)
  89. 		return t->val;
  90. 	else if(sz(t->l)+1 < k)
  91. 		return kth(t->r,k - sz(t->l)-1);
  92. 	else if(sz(t->l) >= k)
  93. 		return kth(t->l,k);
  94. }
  95. const int N = int(1e5)+10;
  96. VII g[N];
  97. int T;
  98. int Start[N],End[N];
  99. int E[N];
  100. pair<II,II> Q[N];
  101. void dfs(int u,int p,int ww)
  102. {
  103. 	++T;
  104. 	Start[u]=T;
  105. 	E[T]=ww;
  106. 	for(int i=0;i<SZ(g[u]);i++)
  107. 	{
  108. 		int w = g[u][i].F;
  109. 		if(w==p)continue;
  110. 		dfs(w,u,g[u][i].S);
  111. 	}
  112. 	End[u]=T;
  113. }
  114. int sqt;
  115. bool cmp(pair<II,II> a,pair<II,II> b)
  116. {
  117. 	if(a.F.F/sqt != b.F.F/sqt)
  118. 		return a.F.F/sqt < b.F.F/sqt;
  119. 	return a.F.S<b.F.S;
  120. }
  121. void print(pnode t)
  122. {
  123. 	if(!t)return;
  124. 	print(t->l);
  125. 	printf("%d ",t->val);
  126. 	print(t->r);
  127. }
  128. int ans[N];
  129. int main()
  130. {
  131. 	int n,q;
  132. 	si(n);si(q);
  133. 	for(int i=0;i<n-1;i++)
  134. 	{
  135. 		int u,v,w;
  136. 		si(u);si(v);si(w);
  137. 		g[u].PB(MP(v,w));
  138. 		g[v].PB(MP(u,w));
  139. 	}
  140. 	dfs(1,1,0);
  141. 	for(int i=0;i<q;i++)
  142. 	{
  143. 		int u,k;si(u);si(k);
  144. 		Q[i].F.F = 1+Start[u];
  145. 		Q[i].F.S = End[u];
  146. 		Q[i].S.F = k;
  147. 		Q[i].S.S = i;
  148. 	}
  149. 	sqt = sqrt(2*n);
  150. 	sort(Q,Q+q,cmp);
  151. 	int L = 2,R = 2;
  152. 	pnode head=NULL;
  153. 	insert(head,init(E[L]));
  154. 	for(int i=0;i<q;i++)
  155. 	{
  156. 		int l = Q[i].F.F;
  157. 		int r = Q[i].F.S;
  158. 		int k = Q[i].S.F;
  159. 		int pos = Q[i].S.S;
  160. 		if(l>r)
  161. 		{
  162. 			ans[pos]=INF;
  163. 			continue;
  164. 		}
  165. 		while(L<l)
  166. 		{
  167. 			if(!(l<=L && L<=r))erase(head,E[L]);
  168. 			L++;
  169. 		}
  170. 		while(L>l)
  171. 		{
  172. 			L--;
  173. 			if(l<=L && L<=r)insert(head,init(E[L]));
  174. 		}
  175. 		while(R<r)
  176. 		{
  177. 			R++;
  178. 			if(l<=R && R<=r)insert(head,init(E[R]));
  179. 		}
  180. 		while(R>r)
  181. 		{
  182. 			if(!(l<=R && R<=r))erase(head,E[R]);
  183. 			R--;
  184. 		}
  185. 		ans[pos]=kth(head,k);
  186. 	}
  187. 	for(int i=0;i<q;i++)
  188. 	{
  189. 		if(ans[i]==INF)puts("nan");
  190. 		else dout(ans[i]);
  191. 	}
  192. 	return 0;
  193. }
Runtime error #stdin #stdout 0s 7716KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/GxynE1
language:
C++14 (gcc 8.3)
created:
9 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!