fork download
copy 
  1. #ifdef __APPLE__
  2. #include <iostream>
  3. #include <cstring>
  4. #include <string>
  5. #include <cstdio>
  6. #include <cctype>
  7. #include <stack>
  8. #include <list>
  9. #include <queue>
  10. #include <map>
  11. #include <sstream>
  12. #include <cmath>
  13. #include <limits>
  14. #include <vector>
  15. #include <algorithm>
  16. #include <iomanip>
  17. #include <bitset>
  18. #include <utility>
  19. #include <set>
  20. #include <numeric>
  21. #else
  22. #include<bits/stdc++.h>
  23. #endif
  24.  
  25. using namespace std;
  26.  
  27. typedef vector<int> vi;
  28. typedef pair<int,int> ii;
  29. typedef vector<ii> vii;
  30. typedef vector<vi> vvi;
  31.  
  32. #define lli long long int
  33. #define ulli unsigned long long int
  34.  
  35. #define PB push_back
  36. #define MP make_pair
  37. #define F first
  38. #define S second
  39. #define ALL(a) a.begin(),a.end()
  40. #define SZ(a) (int)(a.size())
  41.  
  42. #define loop(i,a,b) for(int i=a; i<b; i++)
  43.  
  44. int gcd(int a, int b) {return b==0?a:gcd(b,a%b);}
  45. int lcm(int a, int b) {return a*(b/gcd(a,b));}
  46.  
  47. #define INF 1000000000  //(10^9)
  48. #define MOD 1000000007  //(10^9+7)
  49.  
  50. //FILE *fin = freopen("in","r",stdin);
  51. //FILE *fout = freopen("out","w",stdout);
  52.  
  53. int n, q, maxi=-1, t=0;
  54. vi tree[100010], num(100010), arr[100010], maintain(100010);
  55. vi visited(100010,-1), arrival(100010), vertex(100010);
  56.  
  57. struct SegmentTreeNode{
  58.  
  59. 	int val;
  60.  
  61. 	void assignLeaf(int value)
  62. 	{
  63. 		val= value;
  64. 	}
  65.  
  66. 	void merge(SegmentTreeNode& left, SegmentTreeNode& right)
  67. 	{
  68. 		val= max(left.val,right.val);
  69. 	}
  70.  
  71. 	int getValue()
  72. 	{
  73. 		return val;
  74. 	}
  75. };
  76.  
  77. SegmentTreeNode nodes[400010];
  78.  
  79. class SegmentTree{
  80.  
  81. 	public:
  82.  
  83. 	void build()
  84. 	{
  85. 		buildTree(1,0,maxi);
  86. 	}
  87.  
  88. 	int getValue(int lo, int hi)
  89. 	{
  90. 		SegmentTreeNode result = getValue(1, 0, maxi, lo, hi);
  91. 		return result.getValue();
  92. 	}
  93.  
  94. 	void update(int index, int value)
  95. 	{
  96. 		update(1, 0, maxi, index, value);
  97. 	}
  98.  
  99. 	private:
  100.  
  101. 	void buildTree(int stIndex, int lo, int hi)
  102. 	{
  103. 		if (lo == hi)
  104. 		{
  105. 			nodes[stIndex].assignLeaf(-1);
  106. 			return;
  107. 		}
  108.  
  109. 		int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
  110. 		buildTree(left, lo, mid);
  111. 		buildTree(right, mid + 1, hi);
  112. 		nodes[stIndex].merge(nodes[left], nodes[right]);
  113. 	}
  114.  
  115. 	SegmentTreeNode getValue(int stIndex, int left, int right, int lo, int hi)
  116. 	{
  117. 		if (left == lo && right == hi)
  118. 			return nodes[stIndex];
  119.  
  120. 		int mid = (left + right) / 2;
  121. 		if (lo > mid)
  122. 			return getValue(2*stIndex+1, mid+1, right, lo, hi);
  123. 		if (hi <= mid)
  124. 			return getValue(2*stIndex, left, mid, lo, hi);
  125.  
  126. 		SegmentTreeNode leftResult = getValue(2*stIndex, left, mid, lo, mid);
  127. 		SegmentTreeNode rightResult = getValue(2*stIndex+1, mid+1, right, mid+1, hi);
  128. 		SegmentTreeNode result;
  129. 		result.merge(leftResult, rightResult);
  130. 		return result;
  131. 	}
  132.  
  133. 	void update(int stIndex, int lo, int hi, int index, int value)
  134. 	{
  135. 		if (lo == hi)
  136. 		{
  137. 			nodes[stIndex].assignLeaf(value);
  138. 			return;
  139. 		}
  140.  
  141. 		int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
  142. 		if (index <= mid)
  143. 			update(left, lo, mid, index, value);
  144. 		else
  145. 			update(right, mid+1, hi, index, value);
  146.  
  147. 		nodes[stIndex].merge(nodes[left], nodes[right]);
  148. 	}
  149. };
  150.  
  151. SegmentTree st;
  152.  
  153. void dfs(int v)
  154. {
  155. 	int flag, flag1;
  156. 	visited[v]= 1;
  157. 	arrival[v]= t++;
  158. 	arr[num[v]].PB(arrival[v]);
  159. 	flag= num[v]-num[0];
  160. 	maintain[v]= st.getValue(flag,maxi);
  161. 	st.update(num[v],arrival[v]);
  162. 	loop(i,0,SZ(tree[v]))
  163. 	{
  164. 		if(visited[tree[v][i]]==-1)
  165. 			dfs(tree[v][i]);
  166. 	}
  167. 	arr[num[v]].pop_back();
  168. 	st.update(num[v],arr[num[v]].back());
  169. }
  170.  
  171. int main()
  172. {
  173. 	ios::sync_with_stdio(false);
  174. 	cin.tie(NULL);
  175.  
  176. 	cin>> n>> q;
  177. 	loop(i,0,n)
  178. 	{
  179. 		cin>> num[i];
  180. 		maxi= max(maxi,num[i]);
  181. 	}
  182. 	loop(i,0,n-1)
  183. 	{
  184. 		int x, y;
  185. 		cin>> x>> y;
  186. 		tree[x].PB(y);
  187. 		tree[y].PB(x);
  188. 	}
  189. 	loop(i,0,maxi+1)
  190. 		arr[i].PB(-1);
  191.  
  192. 	st.build();
  193. 	dfs(0);
  194.  
  195. 	loop(i,0,n)
  196. 		vertex[arrival[i]]= i;
  197. 	loop(i,0,q)
  198. 	{
  199. 		int node;
  200. 		cin>> node;
  201. 		if(maintain[node]==-1)
  202. 			cout<< "-1\n";
  203. 		else
  204. 			cout<< vertex[maintain[node]]<< " "<< num[vertex[maintain[node]]]<< "\n";
  205. 	}
  206.  
  207.  
  208. 	return 0;
  209. }
Runtime error #stdin #stdout 0.43s 1531904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0Q97Dm
language:
C++ (gcc 8.3)
created:
7 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!