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. bool anc(int a, int b, int diff)
  38. {
  39. 	for (int i = 0; i < 20; i++)
  40. 	{
  41. 		if (diff & (1 << i))
  42. 			a = jump[i][a];
  43. 	}
  44. 	return (a == b);
  45. }
  46. int main()
  47. {
  48. 	ios::sync_with_stdio(0);
  49. 	cin.tie(0);
  50. 	cout.tie(0);
  51. 	int n, m;
  52. 	cin >> n >> m;
  53. 	for (int i = 1; i <= n; i++)
  54. 	{
  55. 		cin >> ch[i];
  56. 		jump[0][i] = ch[i];
  57. 	}
  58. 	for (int i = 1; i <= n; i++)
  59. 	{
  60. 		if (!vis[i])
  61. 			dfs(i);
  62. 	}
  63. 	for (int i = 1; i < 20; i++)
  64. 	{
  65. 		for (int j = 1; j <= n; j++)
  66. 			jump[i][j] = jump[i - 1][jump[i - 1][j]];
  67. 	}
  68. 	while (m--)
  69. 	{
  70. 		int a, b;
  71. 		cin >> a >> b;
  72. 		int u = a; int v = b;
  73. 		if (a == b)
  74. 		{
  75. 			cout << "0\n";
  76. 			continue;
  77. 		}
  78. 		int diff = dep[a] - dep[b];
  79. 		if (diff > 0 && anc(a, b, diff))
  80. 		{
  81. 			cout << diff << "\n";
  82. 			continue;
  83. 		}
  84. 		if (partofcycle[b])
  85. 		{
  86. 			diff = dep[a] - dep[b] + lenofcycle[b];
  87. 			if (diff > 0 && anc(a, b, diff))
  88. 			{
  89. 				cout << diff << "\n";
  90. 				continue;
  91. 			}
  92. 		}
  93. 		cout << "-1\n";
  94. 	}
  95. 	return 0;
  96. }
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
10 1
2 3 4 5 6 7 8 9 10 1
3 1
stdout
copy 
8
https://ideone.com/hKsG5K
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!