fork download
copy 
  1. #pragma GCC optimize("O3")
  2. #pragma GCC target("sse4")
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. typedef long long ll;
  6. const double PI=acos(-1.0);
  7. #define t1(x)             cerr<<#x<<"="<<x<<endl
  8. #define t2(x, y)          cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
  9. #define t3(x, y, z)       cerr<<#x<<"=" <<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
  10. #define t4(a,b,c,d)       cerr<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<" "<<#d<<"="<<d<<endl
  11. #define t5(a,b,c,d,e)     cerr<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<" "<<#d<<"="<<d<<" "<<#e<<"="<<e<<endl
  12. #define t6(a,b,c,d,e,f)   cerr<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<" "<<#d<<"="<<d<<" "<<#e<<"="<<e<<" "<<#f<<"="<<f<<endl
  13. #define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
  14. #define t(...) GET_MACRO(__VA_ARGS__,t6,t5, t4, t3, t2, t1)(__VA_ARGS__)
  15. //freopen("output.txt","w",stdout);
  16. //freopen("input.txt","r",stdin);
  17. /*-------------------------------------------------------------------------------------------------------------------------------------*/
  18. #define MOD 1000000007
  19. #define endl "\n" 
  20. #define int long long // remove when constraints are tight.
  21. #define inf 1e18
  22. #define ld long double
  23. /*-------------------------------------------------------------------------------------------------------------------------------------*/
  24.  
  25. const int N=2e5+100;
  26. int n;
  27.  
  28. vector<int> adj[N];
  29.  
  30.  
  31. /*
  32. Link to tutorial: https://w...content-available-to-author-only...r.com/community/competitive-programming/tutorials/range-minimum-query-and-lowest-common-ancestor/
  33. */
  34. const int LOGMAX=20;
  35. int T[N];// T[i] returns father of node i
  36. int P[N][LOGMAX]; // P[i][j]= 2^jth ancestor of i
  37. int L[N]; // L[i]=level of node i
  38. void dfs_lca(int node,int par,int level)
  39. {
  40. 	L[node]=level;
  41. 	T[node]=par;
  42. 	for(auto x: adj[node])
  43. 	{
  44. 		if(x!=par)
  45. 		{
  46. 			dfs_lca(x,node,level+1);
  47. 		}
  48. 	}
  49. }
  50. void preprocess()
  51. {
  52. 	dfs_lca(1,0,0);
  53. 	memset(P,-1,sizeof(P));
  54. 	for(int i=1;i<=n;i++)
  55. 	{
  56. 		P[i][0]=T[i];
  57. 	}
  58. 	for(int log=1;log<LOGMAX;log++)
  59. 	{
  60. 		for(int i=1;i<=n;i++)
  61. 		{
  62. 			if(P[i][log-1]!=-1)
  63. 			{
  64. 				P[i][log]=P[P[i][log-1]][log-1];
  65. 			}
  66. 		}
  67. 	}
  68. }	
  69. int LCA(int p,int q)
  70. {
  71. 	//make sure level of p>= level of q
  72. 	// t(p,q);
  73. 	// t(L[p],L[q]);
  74. 	if(L[q]>L[p])
  75. 	{
  76. 		swap(p,q);
  77. 	}
  78. 	// t(p,q);
  79. 	// t(L[p],L[q]);
  80. 	int loglp;
  81. 	for(loglp=1; 1<<loglp <=L[p] ; loglp++)
  82. 	{}
  83. 	loglp--;
  84.  
  85. 	// make p=(the ancestor of p which is at same level as that of q)
  86. 	for(int log=loglp;log>=0;log--)
  87. 	{
  88. 		if(L[p]-(1<<log)>=L[q])
  89. 		{
  90. 			// t(p,log);
  91. 			p=P[p][log];
  92. 			// t(p);
  93. 		}
  94. 	}
  95. 	// now p and q are at same level.
  96. 	// t(p,q);
  97. 	if(p==q)
  98. 	{
  99. 		return p;
  100. 	}
  101. 	for(int i=loglp;i>=0;i--)
  102. 	{
  103. 		if(P[p][i]!=-1 && P[p][i]!=P[q][i])
  104. 		{
  105. 			p=P[p][i];
  106. 			q=P[q][i];
  107. 		}
  108. 	}
  109. 	return T[p];
  110. }
  111.  
  112.  
  113. int32_t main()
  114. {
  115. 	ios::sync_with_stdio(0);cin.tie(0);
  116.  
  117. 	cin>>n;
  118. 	int m;
  119. 	cin>>m;
  120. 	for(int i=0;i<m;i++)
  121. 	{
  122. 		int u,v;
  123. 		cin>>u>>v;
  124. 		adj[u].push_back(v);adj[v].push_back(u);
  125. 	}
  126. 	preprocess();
  127. 	// for(int i=1;i<=n;i++)
  128. 	// {
  129. 	// 	for(int j=0;j<LOGMAX;j++)
  130. 	// 	{
  131. 	// 		cout<<P[i][j]<<" ";
  132. 	// 	}
  133. 	// 	cout<<endl;
  134. 	// }
  135. 	int q;
  136. 	cin>>q;
  137. 	while(q--)
  138. 	{
  139. 		int c,d;
  140. 		cin>>c>>d;
  141. 		int lca=LCA(c,d);
  142. 		int ans=max(0LL,L[c]-L[(lca)]-1)+max(0LL,L[d]-L[lca]-1);
  143. 		if(lca!=c && lca!=d)ans++;
  144. 		// t(c,lca,d);
  145. 		cout<<ans<<endl;
  146. 	}
  147. }
Runtime error #stdin #stdout 0.01s 39332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DqawQY
language:
C++14 (gcc 8.3)
created:
4 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!