fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  7. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  8. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  9. #define rep(i, c) for(auto &(i) : (c))
  10. #define x first
  11. #define y second
  12. #define pb push_back
  13. #define PB pop_back()
  14. #define iOS ios_base::sync_with_stdio(false)
  15. #define sqr(a) (((a) * (a)))
  16. #define all(a) a.begin() , a.end()
  17. #define error(x) cerr << #x << " = " << (x) <<endl
  18. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  19. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  20. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  21. #define L(x) ((x)<<1)
  22. #define R(x) (((x)<<1)+1)
  23. #define umap unordered_map
  24. typedef long long ll;
  25. typedef pair<int,int>pii;
  26. typedef vector<int> vi;
  27. typedef complex<double> point;
  28. template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
  29. template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}
  30. template <typename T> using os =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  31. const int maxn = 1e5 + 100, maxl = 20;
  32. struct myvec{
  33. 	int n = 0;
  34. 	int a[10] = {};
  35. 	inline void pop_back(){if(n)--n;}
  36. 	inline int & operator [](const int &x){return a[x];}
  37. 	inline int back(){if(n)return a[n-1];return -1;}
  38. 	inline void push_back(const int &x){if(n < 10 && x != back())a[n ++] = x;}
  39. 	inline int size(){return n;}
  40. 	inline bool empty(){return !n;}
  41. }vec[maxn][maxl], ins[maxn];
  42. vi adj[maxn];
  43. int par[maxn][maxl], h[maxn];
  44. inline myvec operator +(myvec &v,myvec &u){
  45. 	myvec ans;
  46. 	int i = 0, j = 0;
  47. 	while(i < v.size() && j < u.size()){
  48. 		if(v[i] <= u[j])
  49. 			ans.pb(v[i ++]);
  50. 		else
  51. 			ans.pb(u[j ++]);
  52. 	}
  53. 	while(i < v.size())
  54. 		ans.pb(v[i ++]);
  55. 	while(j < u.size())
  56. 		ans.pb(u[j ++]);
  57. //	ans.n = unique(ans.a, ans.a + ans.n) - ans.a;
  58. 	return ans;
  59. }
  60. inline void dfs(int v = 0, int p = -1){
  61. 	par[v][0] = p;
  62. 	vec[v][0] = ins[v];
  63. 	if(p + 1){
  64. 		h[v] = h[p] + 1;
  65. 		vec[v][0] = ins[v] + ins[p];
  66. 	}
  67. 	For(i,1,maxl)
  68. 		if(par[v][i-1] + 1){
  69. 			par[v][i] = par[par[v][i-1]][i-1];
  70. 			vec[v][i] = vec[v][i-1] + vec[par[v][i-1]][i-1];
  71. 		}
  72. 	rep(u, adj[v])	if(p - u)
  73. 		dfs(u, v);
  74. }
  75. inline myvec lca(int v, int u){
  76. 	myvec ans = ins[v] + ins[u];
  77. 	if(h[v] < h[u])	swap(v, u);
  78. 	rof(i,maxl-1,-1)
  79. 		if(par[v][i] + 1 && h[par[v][i]] >= h[u]){
  80. 			ans = ans + vec[v][i];
  81. 			v = par[v][i];
  82. 		}
  83. 	if(v == u)	return ans;
  84. 	rof(i,maxl-1,-1)
  85. 		if(par[v][i] - par[u][i]){
  86. 			ans = ans + vec[v][i];
  87. 			ans = ans + vec[u][i];
  88. 			v = par[v][i], u = par[u][i];
  89. 		}
  90. 	ans = ans + ins[par[v][0]];
  91. 	return ans;
  92. }
  93. int n, m, q;
  94. int main(){
  95. 	memset(par, -1, sizeof par);
  96. 	scanf("%d %d %d", &n, &m, &q);
  97. 	For(i,1,n){
  98. 		int v, u;
  99. 		scanf("%d %d", &v, &u);
  100. 		-- v, -- u;
  101. 		adj[v].pb(u);
  102. 		adj[u].pb(v);
  103. 	}
  104. 	For(i,1,m + 1){
  105. 		int v;
  106. 		scanf("%d", &v);
  107. 		-- v;
  108. 		if((int)ins[v].size() < 10)
  109. 			ins[v].pb(i);
  110. 	}
  111. 	dfs();
  112. 	while(q--){
  113. 		int v, u, a;
  114. 		scanf("%d %d %d", &v, &u, &a);
  115. 		-- v, -- u;
  116. 		myvec ans = lca(v, u);
  117. 		if(ans.size() > a)
  118. 			ans.n = a;
  119. 		vi vec;
  120. 		vec.pb(ans.size());
  121. 		For(i,0,ans.size())
  122. 			vec.pb(ans[i]);
  123. 		For(i,0,vec.size()){
  124. 			printf("%d", vec[i]);
  125. 			if(i + 1 == vec.size())
  126. 				puts("");
  127. 			else
  128. 				printf(" ");
  129. 		}
  130. 	}
  131. 	return 0;
  132. }
Success #stdin #stdout 0s 103104KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Rbr9TJ
language:
C++14 (gcc 8.3)
created:
8 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!