fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define sz 200100
  4. #define MOD 1000000007
  5. #define ll long long
  6. int ch[sz];
  7. bool vis[sz];
  8. int dep[sz];
  9. int jump[20][sz];
  10. bool partofcycle[sz];
  11. int lenofcycle[sz];
  12. void dfs(int s)
  13. {
  14. 	vis[s] = 1;
  15. 	if (!vis[ch[s]])
  16. 		dfs(ch[s]);
  17. 	else if (!dep[ch[s]])
  18. 	{
  19. 		int v = s;
  20. 		int len = 0;
  21. 		do
  22. 		{
  23. 			partofcycle[v] = 1;
  24. 			v = ch[v];
  25. 			len++;
  26. 		}
  27. 		while (v != s);
  28. 		do
  29. 		{
  30. 			lenofcycle[v] = len;
  31. 			v = ch[v];
  32. 		}
  33. 		while (v != s);
  34. 	}
  35. 	dep[s] = dep[ch[s]] + 1;
  36. }
  37. int main()
  38. {
  39. 	ios::sync_with_stdio(0);
  40. 	cin.tie(0);
  41. 	cout.tie(0);
  42. 	int n, m;
  43. 	cin >> n >> m;
  44. 	for (int i = 1; i <= n; i++)
  45. 	{
  46. 		cin >> ch[i];
  47. 		jump[0][i] = ch[i];
  48. 	}
  49. 	for (int i = 1; i <= n; i++)
  50. 	{
  51. 		if (!vis[i])
  52. 			dfs(i);
  53. 	}
  54. 	for (int i = 1; i < 20; i++)
  55. 	{
  56. 		for (int j = 1; j <= n; j++)
  57. 			jump[i][j] = jump[i - 1][jump[i - 1][j]];
  58. 	}
  59. 	while (m--)
  60. 	{
  61. 		int a, b;
  62. 		cin >> a >> b;
  63. 		if (a == b)
  64. 		{
  65. 			cout << "0\n";
  66. 			continue;
  67. 		}
  68. 		bool usecyclerev = 0;
  69. 		if (partofcycle[a] && partofcycle[b])
  70. 		{
  71. 			if (dep[a] < dep[b])
  72. 			{
  73. 				swap(a, b);
  74. 				usecyclerev = 1;
  75. 			}
  76. 		}
  77. 		int u = a;
  78. 		int v = b;
  79. 		if (dep[a] < dep[b])
  80. 		{
  81. 			cout << "-1\n";
  82. 			continue;
  83. 		}
  84. 		for (int i = 0; i < 20; i++)
  85. 		{
  86. 			if ((dep[a] - dep[b]) & (1 << i))
  87. 				a = jump[i][a];
  88. 		}
  89. 		if (a == b)
  90. 		{
  91. 			if (usecyclerev)
  92. 				cout << (lenofcycle[u] - dep[u] + dep[v]) << "\n";
  93. 			else
  94. 				cout << dep[u] - dep[v] << "\n";
  95. 		}
  96. 		else
  97. 			cout << "-1\n";
  98. 	}
  99. 	return 0;
  100. }
Success #stdin #stdout 0s 4312KB
comments (?)
stdin
copy 
12 2
2 3 4 5 6 2 3 7 8 8 12 11
7 6
11 5
stdout
copy 
4
-1
https://ideone.com/pi9Cx3
language:
C++14 (gcc 8.3)
created:
3 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!